The redesign took about 2 weeks (or more but with long brakes). I've modified the aspx files (html) to have a tableless design (I use tables where they are needed), wrote the CSS. Basically the UI was done from scratch.
Then came the part where I had to compress the output (html, css, js and viewstate). The HTML was done with VS where I've removed the formatting (most of the controls are on a single line). For the CSS I've used an online css compressor and for the js the script manager knows how to do this. The view state is on all of the controls and you need to add an EnableViewstate = "false" to the main user controls (category navigation, menu, header, footer) or to individual controls (links, labels, a.s.o.).
I still need to add a HTTP compression module because of the web forms.
Indeed nopCommerce is very flexible. You can change the UI easily to suit your needs (I've changed all the markup and CSS for this store) and other code behind modifications can me made with minimum effort because the code is well commented and elegant.