USB2 powering 3.3V at 500 mA
Why isn't there a device that negotiates for 500mA, and then simply delivers it at 3.3V @ 750 mA (or close)?

Getting 750 mA implies a switching regulator, which is going to be a few components.
If you just want 500mA, I believe officially you are supposed to enumerate if connected to a host. However, almost nothing actually enforces that requirement, so if you are really pressed for board space or don't mind using a USB phone charger, you could omit the microcontroller and put a 30 cent 3.3v linear regulator.