Well it will not be easy if this would be your first skin but I don't see any real problems for a good skinner. (But I only spent a few minutes on the site...)

I wouldn't use the default menu, but Housemenu or another CSS menu, especially for the top menu.

You could re-create this site using customized skin, container and page templates.  Using the SEO Menu you could have your page templates be created with the set navigation and with the reusable content.

I think you could tweak the existing DNN menu to replicate the TOP NAV too without too much trouble.

Just quickly went through the site, by using SEO Skin Object you can drop many navigation menus on the page template. 

So yes it's possible and of course the more experience you have using DNN and skinning techniques, the easier it will be, but if you are just starting out, I wouldn't be too afraid of the task.  There is a learning curve, but it's not daunting.

Jerry