When I read Andreeson's comments, I get the sense that he's very bitter about things. The statement that stands out, though, is
"There hasn't been any innovation on the browser in the last five years. And five years from now there won't be any changes"
I had some thoughts on the subject I posted to slashdot earlier but they came down to a couple of fundamental things:
1. We have fantastically powerful computers and incredibly stupid users. A browser with a little bit of AI for pattern matching might go a REALLY long way to solve the idiot problem. Case in point: Teaching people how to build a PC, I show them five different web sites where parts can be purchased. A half-dozen people literally come back to say "I didn't know how to use the site" - literally, that they couldn't follow the catalog metaphor that most commerce sites use. Even something as simple as finding a "Support" page can be a real trial for some folks.
2. Bandwidth throttling. Why doesn't my browser understand that, if I'm downloading an image at 1kb/sec, that my connection is slow, and perhaps downloading 15 other images, a java crapplet and a .swf is not the best thing that it can do?
Those seem to me like great ways browsing could be improved.
Prof, Moz and IIRC Opera both have skins support. I'm not sure how it helps the browsing experience, but it's there.