Frankly, the conversation is far from compelling and doesn't really add up to the headline. Sure you can think of improvements over the back button, but what Andreessen suggests (a graphical tree browser) doesn't look visionary to me.
Another thing that shocks the former Netscape folk in me is the only reason he invokes for using such or such browser:
I'm using Mozilla pretty much full time. I switched six or nine months ago. I had been using IE for three or four years before, because it was rendering page views faster. But now Mozilla does it faster.
Well, if I can appreciate that speed (or lack of) can be a big factor, a word on standards would have been nice to hear, especially from him. Ironically, if speed is just what Andreessen needs, then he should be less contemptuous about Safari.