What layout algorithm are you using for graphviz? sfdp is less computationally intensive than dot/neato/circo, and I would have thought it would be able to cope (assuming you have enough RAM/swap) - this gallery [1] uses graphviz to visualize networks from the University of Florida Sparse Matrix collection, the largest of which "have tens of millions of nodes and over a billion of edges".

Gephi and Cytoscape are the main free graphical applications for analyzing networks; they might work for you. Tulip [2] might also be worth a try.

[1]: https://web.archive.org/web/20111102185002/http://www2.resea...

[2]: http://tulip.labri.fr/TulipDrupal/