I have loved the MDK series. The first one is a dark, depressing, shooter / puzzle game.
The second one, however, is even better.
It is one of those games that you will react to a lot, hopefully. There is a lot of varied humor. It will frustrate you. It will challenge you. It will reward you. The game's three distinct characters go three distinct routes.
http://www.youtube.com/watch?v=p4Sb9_ow_Xg&feature=plcpOnly thing the trailers don't show is just how awesome the professor makes some crazy things, or just how epic the the stealth suit guy is at sniping.