Given the two choices you noted, I'd go with the 25-06. Plenty of power for deer, very flat shooting, accurate. Would make a great coyote rifle as well.
However, you might want to take a look at two others you didn't mention, the .243Win.
and the .260Remington. The .260 is plenty for deer, and would also be good on varmints
including coyote. If you handload then this is the one I'd give serious consideration.
It's available in some nice light rifles too. The .243Win. is, IMHO, a minimum for deer, but will do, and would also make an excellent varmint rifle. Very accurate, and also
available in light rifles. Come to think of it, if you handload, take a look at the .257 Roberts. It's available in the Ruger Ultra-Light (6lbs., 20"barrel). Recoil with the .257 is
mild. Factory ammo is available for the heavier bullets for deer hunting, but you'll need
to load your own for varminting. Another option in the same rifle is the old .270Win.