Second Ethan's suggestion for EZ-Anchors, except I prefer the metal ones - I find with the plastic ones, either the screwdriver slot strips out too easily if the going gets tough (thick layer of paint or wallpaper, for example), or the tip mushes out before it penetrates (ditto).
Of course, one of the gotchas with these is when you run into a stud with them, and then you have a big hole chewed out... if the site has wooden studs, however, you can use these, and they'll drill right into the wood:
For more holding power, toggles are great, but you're back to the two-stage procedure of drilling a BIG hole first... instead, how about something like this? They drill in like a standard EZ Anchor, then the toggle opens up when you drive the screw in:
There are other variations on the design where the tip splits apart (similar to in Ethan's picture) or in other ways improves the holding strength. Note that ANY type of wall anchors - be they for hollow wall, brick, concrete, etc. - should list what weight they're rated to support, so you can compare based on your requirements.