I upgraded my 3G to iOS 4.0 and then unlocked it so I could sell it more quickly on Craigslist. I can't speak to app compatibility (as I wiped the phone), but it seemed to run fine.
EDIT: Just wanted to add it was my first time jailbreaking an iPhone and it was incredibly simple...took like 10 minutes.