Generally, to be close to Ol' Wily, you either put out some sort of bait, or you use a call. A call can be either mouth-blown or electronic. If you're moving around, it's pretty much only in open country that you might see a coyote before he sees or hears you. In thicker brush or woods, the odds are all on his side.
If you're proficient, a shotgun with slugs works to maybe a hundred yards. Closer in, it depends in part on the choke, but #2 on up to 00 will do. Over that, a rifle. It doesn't take much; the average coyote is somewhere in the range of maybe 25 or thirty pounds on up to rarely much above 40 or 45.