Okay, so here's the trick to getting good gifts. They don't have to be expensive in an absolute sense, just a relative sense. Sometimes the best gifts are those little luxuries we deny ourselves. Would you ever spend five bucks on yourself for bath beads from H20? Cruise places like Pier One, CostPlus/World Market, etc and try to look at things through those sort of eyes. Think:

"I always wanted to try this but it was double the price of something comparable..."

A nice funky frame is great. Also think consumables. No one needs another knick knack or coffee mug for the bookshelf but some chocolates, scented candles, soaps, bath products, quality olive oil, exotic hot sauce, smoked salmon, etc are great because they can be made to disappear. Got a friend, relative who is job hunting? Some nice heavy, high-rag content paper is great for sending out resumes, cover letters, etc. For the computer geeks in your life, what about burnable CDs that come in exotic colors or a mouse pad with a decent wrist rest?

Art gallery gift shops are another good hunting ground. When the hell are you ever going to buy yourself something there? Never. That's when. Never. Once I had great success by giving my cousin $40 worth of expensive wrapping paper from the art gallery. Yeah I wrapped wrapping paper. It's a great gift two fold:
  1. When you need wrapping paper, usually you don't have any and that's a pain
  2. When you run out to Wal-Mart to get paper, you linger over the expensive stuff, and then buy the 99 cent roll.

Or why not think green? I find a lot of people are hesitant to try those fluorescent light bulb replacements because they're pretty expensive and people don't want to spend $5 on a light that they fear will turn everything a shade of blue. Or think safety. A carbon monoxide detector can be a life saver but a lot of people tend to pass those over more pressing needs. Or think fluffy! Think pillows! When would you ever spend $20 on a nice pillow for yourself? Check out the funky part of town. Lots of funky boutiques have nice hand-made pillows.

If your relative/friend does a lot of traveling, why not look into getting them some neat compact plastic bottles they can put shampoo/conditioner/toothpaste in? Most people tend to skimp there and use old film canisters and stuff. Or alternatively a nice funky toiletries bag can be cool. Most people just end up shoving their leak-ables in a plastic grocery bag.