You seem to have already found where to turn off the standard categories menu, whether it was categories-tabs or categories sidebox you meant.
To remove the navMain bar at the top of the header, open /includes/templates/your_template/common/tpl_header.php and comment out the first "navigation" section. If you want to be more specific and just remove those two links leaving the headerbar, you can delete the <li>...</li> items in question.

Sorry to be complicit in the hijack:)