I agree that Dia and to many extents Kivio really suck for diagramming and Visio really is (dare I say it) a best of breed application (probably since it was a purchased and not originally developed app by MS).
As for MS Project, have you looked at OpenProj? http://openproj.org/openproj it's available under the CPAL which I believe (haven't verified) OSS license. It reads and rights MS Project files just fine and appears to have all the features that I associate with MS Project. Granted, I'm not a project manager so I really don't use most features but the PMs that I've shown it too all seem to think it's just as good.