You correctly note that it matters by print size. Future Shop actually tries to enforce 120 pixels per inch, which is likely somewhat lax. 150 might be a better guide. For production work, many magazines want "300 per inch".
Along this line - I don't know about the other online stores (and there are several) but Future Shop also offers a "letterbox" mode, where the entire digital image is printed with white edges to fill to the size you chose. I've never seen this option on film prints, even though the problem strictly exists there as well. This is notable because it maximizes the pixels printed for a given image/size combination.
As long as you expect to send your prints directly as-is to the printer, then this is a reasonably guideline. I have some nice 8x10s shot using the 2 megapixel HP.
However, the "quality of film" is closer to 6 megapixels for 35mm. This is the number that would matter if you expect to treat your 'digital megatives' like your film negatives. The catch is that common operations, like cropping, may drastically reduce the pixel size of an image.
This is the reason I now pay much more attention to the frame when shooting. Digital pays off when you can crowd the frame and use tight composition.
There is one other caveat - my experience is based on one camera! As a suggestion - do a rough scan of the market, and see if you can get a low-cost multi-format card reader (something you will want anyway) and get a small Compact Flash and Smart Media card, and one of any other card you might use. This sounds like overkill, but it lets you ask to try cameras in store, using your cards, and take the resulting images away for evaluation. To be fair, you'll need nice store personnel to do this, but it lets you learn a lot about the images before you buy.
For full effect, take a small portfolio of standard images - magazine clips, nice 8x10s, some artwork - and includes those for your test shots. Although not representative of regular material, it will give you some common reference points to compare images.
On the other hand, if all this seems like it's not giving you what you expected, think about shooting and printing 35mm, and then going digital with a nice scanner.
He makes a very good point about bringing in a memory card and some standard images when shopping for a camera. It's the equivalent of always bringing a familiar CD when shopping for a stereo. Thanks again, Chris.