"Tavern Tasty Meats" - that's a great name! Sounds like you have a great source of good, local GF meat.
Slowly introducing Paleo eating will be easier if you do a lot of the cooking and make easy meals that taste good. Your wife will buy in to the idea if she is confident that she will still be eating tasty stuff. I didn't have to convince my wife (she already ate Paleo), but I am going thru these steps with my parents, who really need to eat a good diet at this stage in their lives!