Andreesen views Bitcoin in a similar context to personal computers in 1975 and the Internet in 1993 - an emerging new technology that idealists love, the establishment scorns, and technologists are transfixed by, that ultimately becomes mainstream with profound effects.
To understand why, Andreesen explains why Bitcoin is such a big deal breakthrough from the computer science perspective: it solves the so-called "Byzantine Generals Problem" [BGP]. What is the BGP? It originates from a paper that examined the hypothetical problem of how in the Byzantine era generals surrounding a city could cooperate battle plans when they can only communicate by messengers, one or more of whom may be traitors trying to confuse them; in essence, the issue is how to establish trust between otherwise unrelated parties over an untrusted network, whether generals laying siege to a city or people communicating via the Internet. Bitcoin solves the BGP problem, which means for the first time, one Internet user can transfer a unique piece of digital property to another Internet user, guaranteed safe and secure, where everyone knows the transfer has occurred and no one can challenge its legitimacy. Ultimately, this could allow the transfer of significant digital property - digital signature or contracts, digital keys, digital ownership of physical assets, or digital ownership of stocks, bonds, and money - without requiring a central intermediary like a bank or broker.
The removal of the intermediary matters so much not just for security purposes, but because it means all of these transfers can occur with little or no fees, in a world where existing payment systems often charge fees of 2% to 3% (think credit card interchange fees that vendors/businesses typically absorb).
While so far Bitcoin has been incredibly volatile and speculative, Andreesen notes that its speculation may actually be accelerating its ability to be adopted mainstream as well, and even if it's not stable as a currency it may still be effective as a payment system, not only because it has near-zero costs, but also because it eliminates the risk of credit card fraud (for instance, the Target credit card hack couldn't have happen with a Bitcoin currency system). In addition, Bitcoin also facilitates international transactions and money transfers (the system isn't US specific), and micropayments (think $1 or even $0.01 transactions, feasible with a no-fee payment system).
As Andreesen notes, there is no shortage of regulatory and other issues that still have to be addressed with Bitcoin, but the bottom line is that Bitcoin is a way, way bigger deal than "just" about some new speculative digital crypto-currency.