From a HTML/CSS point of view, the flexibility and freedom in creating custom design packages from scratch seems to end beyond phtml files.
In this case, I'm trying to add custom css classes to list items inside the Top menu unordered list. But it seems that inside topmenu.phtml, those list items are present inside:
<?php echo $_menu ?>
Question:
What is the easiest and most upgrade friendly way to achieve this in Magento without the help of thirth party extensions?
After googling for half a day, I came accross several complex potential solutions that need deep xml and php customizations.
Is adding simple css classes really that devious inside Magento?
[EDIT]
Yes it is that devious in Magento 
Some html in Magento is generated by PHP and therefore in certain cases, adding custom CSS classes and ID's can only be added by customizing PHP files.
In this case, for adding CSS classes to the top menu category list items. A custom version of Topmenu.php is needed:
app/code/core/Mage/Page/Block/Html/Topmenu.php
[/EDIT]
Please correct me if I'm wrong.