Shadow of the Colussus is a great game. The concept of playing an entire game through a series of epic boss battles is superb.
I think some of bond1's recent work is boss battle worth e.g. Dante beast, Ice Wizard, Chainsaw Brute etc.
Not only are they bigger than most FPSC characters but they have custom animations, multiple attack patterns and good AI which is essential for a good boss fight. Not just giving something loads of energy and attacking power.
The Ice Wizard is cool like when he freezes you and the player becomes stuck with a hud making it look like your in a block of ice then melee attacks you.
Bond1 got long and short range attacks down. I would like to have seen a boss with short, medium and long range attacks such as a super soldier that throws grenades from distance, shoots a gun when in range and uses a knife for melee etc. That would be possible in FPSC.
Something I'd really like to try for a boss in FPSC is something that has environment awareness. For example something that can climb segment walls and hang from a ceiling or jump from ground level up to a 2nd layer. I think that might be possible as there's already been a spider made for FPSC that can crawl along any side of a standard segment surface. See link
http://www.youtube.com/watch?v=h8nY-r7Hxrk
Would be nice to see more FPSC bosses. They help break up a level and if done properly can make a game far more memorable.