You’re trying to kills to birds (or critters in this case) with one stone. In either case, you can end up over gunned on one, or under-gunned on the other. While the .22 centerfires are legal for deer in many states, and they are potent calibers for coyotes, they are generally considered under-gunned for deer. Conversely, the .30 caliber centerfires are well-suited for deer, but are severe over-kill on coyotes. By all means a .30 caliber will kill a coyote right dead, and depending on the favor of round, i.e. .30-378 Wea. Mag with a 130 grain Nosler Ballistic tip will kill it, skin it and grind the burger all in one trigger pull.
That leaves us to consider the basic calibers available that are not to the extremes. They include the .24 cal, 25 cal, 26 cal, 27 cal, 28 cal. Most any of the rounds in these calibers will fill your needs, and some will do a better job than others. These basically break into short cases, long cases and magnum cases. You don’t need a magnum in any of these calibers. A long case (long-action) in 25, 26, 27, 28 and 30 calibers is more than enough for the job to 500 yards if you do your part. The 24 calibers are getting stretched a bit at 500 yards, even the 6mm Rem and .240 Wea. “Mag”, which “Mag” it is not truly…not in my book.
Other considerations include that the larger the caliber the higher the cost, both in financial terms and in recoil terms. The smaller, faster calibers tends to erode barrels more quickly. For example, a hot loaded .25-06 Rem will not last as-long-as a hot-loaded .30-06 Sprg. Yet, they have the same parent cartridge. As I see the long-action cartridges, you would be hard-pressed to find more effective and more efficient rounds than the following: .25-06 Rem; .270 Win, .280 Rem, or .30-06 Sprg. These are all over kill on coyotes, and Hades on deer.
The last category is the short cartridges (short-actions) such as the .243 Win; 6mm (.244) Rem; .260 Rem; and the 7mm-08 Rem. Any of these calibers will knock a deer down with one well-placed round. I have used them; they work plain and simple. Any of these cartridges are fine rounds for coyotes to 500 yards with no worries of remaining energy for a one-shot, clean kill.
If you are new to shooting, I would encourage go shooting with friends, and see your tolerance. More gun ain’t gonna kill what you can’t hit because you become recoil-sensitive. You need to decide the typical distances that you will be engaging in hunting. For me, shots to 525 yards are not uncommon. Depending on where I hunt, I take a .308 Win up to a .300 Win Mag for deer. For coyotes and other varmints I take a .223 up to a .270 Win. Again, I shoot at some long distances, and have been hunting since around age 10ish. For what it’s worth, I’ve never felt under-gunned with my 6mm Rem!
My final insight: it aint’ the caliber, or the gun that much matter. What matters is your knowledge and commitment. Learn you gun. Learn your caliber and it’s trajectory and drift. Keep practicing until you develop a good clean ability, then keep practicing to maintain that ability. That will make you and effective, efficient hunter. I know I’ve droned on more than needed, but you asked a serous question and I wanted to give you a serious answer.
One of the best deer/varmint rounds I ever used was my Sako Finnbear in .270 Win. I used 130 grain projectiles on deer, and 90 Speer hollow points and Speer 100 grain Hotcores for varmint. The reason I used that large of a caliber for varmint is that is what I used for deer. It kept me skilled year round with my one rifle. When you can hit 6, 2-liter Coca-cola bottles filled with water at 500 yards, with 6 shots, you have your skills honed. If the rifle hadn't possessed enough accuracy potential, or I hadn't possessed the commitment to practice, I wouldn't have hit anything. My personal assessment as to how far I can ethically shoot game, is how far can I hit 100% on 2-liter bottles filled with water? For me, that answer is 500 yards.
Why do I use that assessment? Simple. A woodchuck looks a lot like a 2-liter bottle at 500 yards when they stand. A coyote's chest area is about the same size. A deer heart/lung area is about that size.
Let us know what you decide.
Geno