Beef and turkey leg for Christmas: what cut, and where? (Baltimore)
Hollins Market and Lexington Market have stalls that sell turkey legs and other turkey parts, including giblets. Lexington Market also has smoked turkey legs.
There is an alternative to the prime rib, the chuck eye roast. The prime comes from ribs 6-12, while the chuck comes from ribs 1-5.
Since Trueths is also an abattoir, they'll be able to give you the exact cut that you want.