Starting points for free skins:
http://www.dnnskins.com/
http://www.alldnnskins.com/
http://www.xd.com.au/free+skins.xd
Also try Google for "free DotNetNuke skins".
You don't have to decide on your menu layout until you really want to. That's the beauty of DNN. You can tweak, rearrange build, rearrange etc etc. I often go back and forth between skinning and building. Personally I've found that I like building the navigation for the site first without much consideration for the design. Once I get the architecture down I start thinking about what I want it to look like and start working towards that. Then when I have an idea of layout and a DNN skin ready I'll place and skin modules to fit the design. But it's totally subjective and boucing around is encouraged (just keep in mind that once you commit modules to a pane in your skin that the database is going to be looking for that pane, so you'll want to never change the names of the panes in the skin once they have modules, but you can add new panes).
You'll find once you've gone through a bit of learning pain that DNN is pretty cool indeed. These forums are a life saver when people actually reply. Mitch Sellers and Timo Brumelhoff (sp?) are very knowledgable and have saved my ass a couple of times. If you have any other questions let me know and I'll do my best to help.