Via Matt Asay, I just learned about OpenProj, a free, cross-platform, open source alternative to Microsoft Project. Despite needing a little GUI polish on MacOS X (it uses a retro-Copland theme), it's very impressive. If you are a heavy Microsoft Project user, I wouldn't recommend switching to OpenProj, but if you work in a cross-platform environment (Unix, Windows, Mac, Linux), or if you only need to open or edit Microsoft Project files on an occasional basis, it's definitely worth a look. OpenProj is maintained by Projity, a firm which also offers subscription access to a web-based project tool, Project-ON-Demand, which uses a SaaS (Software-as-a-Service) model.
Now, where can I find a good, cross-platform, open source Visio replacement?