Well, the way a large print comes across depends on your viewing distance. Take one of your images that is visually appealing and is also good and sharp/crisp and view it in Photoshop using "Actual Pixels" (100%, Ctl-Alt-0) then move back a bit, and you decide.
Another good test is to crop a small portion of your image, one that would fill, say, an 8x10 portion of your planned print, and print it as an 8x10, and then view it from a distance that you would normally view the print, and you decide.
You can get away with good, large prints as long as you are viewing from a reasonable distance. I hang my walls with 12x16 prints made from 4-6 MP images from old P&S cameras from a few years back. They are visually pleasing images, and they work. Get real close and you can see the finer detail "breaking down", but that's real close. Then, I have 12x18 prints of shots from my old 8MP 30D where I can get up close with a magnifying glass, and the fine detail stands out very well.
The thing is, they all hang together. Some of the 4MP prints will bring out "Wows" from people that see them. They may not be gallery quality, but still...they are ones that have been "picked" by actual viewers.