Advice on choosing and customizing a theme

Hi;

I’m new to blogging, wordpress, and pHp, but I am a long time forum junkie and programmer.

I would like a theme ( dark colors ) that has a traditional side bar, but also a navigation link bar in the header that I can use to integrate my blog with the rest of my web site.

I’ve seen maybe 1-3 themes like this, but I wasn’t thrilled with any of them.

In terms of picking a theme to start off with to customize, am I better starting off with a sidebar theme and putting in my own navigation bar or am I better off starting off with one of the few that has a horizontal navigation bar in the header and creating my own side bar.

Thanks for any advice!

Steve