Its not where you put them that'll have any real impact. Its how you style them. Because you have no work visible its impossible for me or anyone else to offer suggestions.
Take a look at other websites, designs, magazines anything... and work out the reason WHY you like something. Just liking it is not enough you need to put reason to your emotion and then you'll be able to offer the same experience without feeling the need to copy something already in existence
When im designing for web I rarely look around for ideas once Ive actually started, it just flows but thats usually because Ive spent a lot of time browsing portfolios and subconsciously coming up with ideas. .
A good place to start looking for ideas would be templatemonster.com - I go there every now and then because although theyre templates the standard of work is usually very high and its easy to flick through hundreds of designs without having to go all over the place.
This is a very, very vague question and as such I don't think you'll get the definitive answer you're looking for. It's vague as there are so many options of how you could display your navigation, as you said in your post the most popular are horizontal underneath the header or left side menus.
I think you're tackling your own site design in the wrong way IMO, go back to pen & paper and sketch out ideas for your site layout, considering all the content you want to display, what pages the site will have and therefore what items you need in a navigation. Be creative, put some ideas together then jump into Photoshop or similar and start putting a design together.
I think what Bren was trying to point out is you're a designer, so come up with some ideas, if you posted a couple of ideas you had thought of, in sketch form or visuals you'd get some comments/feedback. At the moment it's like asking how long is a piece of string
take a look at Sexy Web Design - SitePoint Books you can download the first 2 chapters as a preview. Within these first two chapters are some suggestions on navigation and how to go about thinking of functionaloty that you might find helpful.
I read it and whilst there was an element of 'stating the obvious' it was a good reminder as I often get stuck in my ways and overlook the obvious!