Just got my first Mac, a new MB C2D...
Had it been a new PC, I would have reinstalled a new fresh OS without all the small apps and exactly as I want it. Is this recommended for a new Mac as well?
Also, do you recommend installing a firewall? I have understood that Anti-virus shouldn't be required.
Welcome to the Mac family!
There should be no reason to do any OS reinstall with a new Mac as there are only a very few things that you might want to leave out (possibly all of the extra language packs -- these packages do not impact on performance anyway, they just take a little space on the drive). The only people that I have bumped into that reinstall their OS are audio/video professionals who need a very lean system and will only install the bare minimum core plus the DAW or Video software. For 99.99999% of other people (professionals included) a reinstall gains them nothing except to save a little disk space.
A firewall is always a good idea. Although the core of Mac OS is Unix and is very well configured out of the box for security, having a physical (as opposed to software) firewall makes an already secure system extremely difficult (nothing is impossible but this configuration comes close) for anyone to gain unauthorized access to your system.
Viruses are not a concern with Unix based OSes due to the fact that nothing can run without your permission and even if you loaded something (viral) in on your user account it can't damage anything critical as nothing at the user level can access root level system items (root level items cannot be written to, or damaged, from the users account without authorization from the user). The only real way for a virus to gain access to your system is for the virus writer to have local physical access to your computer (in other words he/she is sitting in front of your computer) and have root privileges, or know your password in order to invoke "sudo", and then to manually enter the virus. Do not waste your money on _Anti-virus_ software for the Mac.
Enjoy your new Mac.
Sopranino