Ability to open (and maybe save) various Directed Graph formats, and draw the graphs implied (with some dialogues to control symbols used).
e.g. GraphML, TGL, and also Directed Graphs using Excel data/CSVs. (Use yfiles yed and DOTTY as examples for functionality and file formats to support).
And also an ability to graph Ontology definitions/use Ontologies as data inputs similar to Excel (both using OWL file format, using Stanford Protégé 3.x and later as a reference.)
This would make Visio much more useful as a visualisation tool for various use cases include Reference Enterprise Architectures (and allow Visio diagrams to be "inspected" for alignment to reference architectures)
The Visio 2010 & later "Containers" feature is a baby step towards directed graphing.
It would be acceptable for this capability to only be available in "Pro" versions, or maybe even "Visio for Enterprise Architecture" special version (although a special "EA" version would also require an ability to interact with a shared repository, perhaps a special schema set up in Sharepoint to justify an extra cost license).