For modern games, the Xbox360 controller is your best option, as it's the best controller out there and reasonably well supported right out of the box. If you need more configurability, you can use xboxdrv instead of the build in kernel driver. The wired USB version is also pretty cheap.
The Dualshock can work over USB instead of Bluetooth. Support for it is however a bit flunky, as each button on the thing is reported as both axis and key event, which confuses most games. xboxdrv should however be able help with that, Qtsixa might as well.
As for the OnLive controller, no idea. Given that it comes with an USB dongle, there is a good chance that it will just work out of the box like any other USB device, but I don't have any experience if that is actually the case.