Wow, NO ONE mentioned General Guy. General freakin' Guy, the boss that'll keep fighting till the end, the boss that spouts inane dialogue when he orders his troops. He was the best boss in Paper Mario next to Tubba Blubba.
Fawful was also pretty hilarious. Hopefully he makes a comeback in Mario & Luigi: Partners in Time or I'll be super ticked off.