243 would probably be the most practical, as I think all states with centerfire deer seasons allow them. The states that dont have a minimum caliber requirement then I would pick a 22-250 which is my favorite. The biggest benefit it has, largest cartridge you can watch bullet impact with, which is a must on a p. dog town.

I gave my son a 243 for his first rifle because of the deer hunting issue and yet provides days of blasting prairie dogs with ease too.