Automatic distinction between PC-USB and Wall Adapter-USB

Although I don't have direct experience with this, from what I've read, IC's that perform this function usually sample the D+/D- lines on application of power with some sink on the D+/D- to detect the charger type, and disconnect their detection logic once a determination has been made of the connected source, AC adapter or USB port. More information is available from a TI app note here.

I sure from my previous part searches that some battery charger IC's have built in charger type detection, but I couldn't find an example part when searching just now.

There's the MAX14578 which also does the job, but it may not fit your criteria of low cost.

A DC-DC boost converter like the ones you're seeing on eBay doesn't do what you want. It converts low voltages (1-5V) to 5V for charging devices over USB. That would be useful to charge a USB device from a battery.

What you want is an AC to DC converter which can take an input voltage of 110V and output 5V / 500mA (although you'll find that 500mA doesn't charge a modern phone particularly quickly, so you might need something beefier). To charge at 500mA a USB charger doesn't need to have much more than 5V connected to a USB plug. To charge at a greater rate (modern phone chargers charge at up to 2.1A) the circuitry needs to be a little more complicated.

Every plug-in phone charger (from a reputable company) does what you want (including the necessary circuitry to negotiate a higher charging rate). The problem is, pulling one apart to build into a lamp that you sell would be ill-advised. Given that there's mains voltages present I'd imagine there's all sorts of liability issues.

The problem isn't particularly complicated as electronics go, but given the voltages involved and that you're planning to actually sell these devices it might be worth talking to an electronics engineer. Poorly designed mains voltage AC to DC converters have killed people before - this is something that you want to do right.