Assuming that you have quality glass and especially that you do your part (ie capture technique, focusing is dead on the money, post processing technique and printing methodology are all up to top caliber standards), it's feasible to make many - but not all - 16x20 or 16x24's from even a 4mp camera. I've seen prints shot by the track photographer at Laguna Seca that were done with a 4mp Canon 1D, and most of us would have a hard time believing that they didn't come out of something more like a 12mp or 16mp camera. But that's only what's possible - most of us can't do that well.
More realistically, if you do a good but not fanatic job, use good glass and have good scaling software (Genuine Fractals, QImage, BlowUp for sure), you can definitely make 16x20's comfortably and even larger if you're careful from a 10/12mp file. I don't think Walmart/SamsClub will take anything bigger than 8x10, but the quality printing houses (I have used White House Custom Color, whcc.com) usually will handle anything that you can send them. whcc has regular price list items to 30x45 and you can do larger stuff at $/sq ft prices.
_____ Brian... a bicoastal Nikonian and Team Member
My gallery is online. Comments and critique welcomed any time!