Data.gov should have a faceted search interface that provides a comprehensive overview of Data.gov content (metadata and facet counts), and a way for users to progressively refine their search criteria. Faceted search provides a good way for outsiders to better understand a big collection described by complex metadata structure.
The faceted metadata should also be shared as an Atom Feed, so that updates of new content can be retrieved. Search results should also be presented in multiple formats, including paged Atom feeds, allowing users and developers to obtained updated lists of search results. (See an example work-in-progress: http://opencontext.org/about/services).
Right now Data.gov is a pretty looking file-server. Some of the datasets in Data.gov are dynamic, and these datasets should also be available as a service, since it would be nice to have a reliable source of updated information. RESTful access to dynamic data would be fantastic, and GData and Microsoft's new OData may be nice models.
Finally, Data.gov developers should really tap into an enthusiastic and talented educational community. The UC Berkeley School of Information has a clinic (that I run http://isd.berkeley.edu) that can help with a variety of Data.gov issues (esp. usability, metadata, service design, uetc.). Working on Data.gov would provide students with excellent "real-world" design experience while at the same time help Data.gov better achieve its mission.