Google Uncle Sam was a search engine that I used time and time again when I was taking a Government Documents class in library school. I actually enjoyed that class very much. It was a tremendous amount of work, but I really got into it. Two of the other very useful resources in the world of free niche search engines that I used while taking the class were the Government Printing Office's (GPO) GPO Access site and FirstGov.gov, the United States government's official web portal.
Apparently the United States Government Manual is questioning the popularity of Google Uncle Sam because Google Uncle Sam doesn't include all U.S. federal government information. Not all federal sites have the .gov or.mil domains. For example, the United States Postal Service has a .com domain. One of the other complaints that the U.S. Government Manual has is that Google Uncle Sam does not have an Advanced search function.
FirstGov. does offer those features. FirstGov. has become more of a directory-based site. It allows users to search federal sites and state and local government sites. FirstGov. also permits users to search entities such as the U.S. Postal Service and National Defense University. Two enties without the .gov or.mil domain. FirstGov. also has an advanced search function. Some of the things that FirstGov doesn't have that Google excels at are relevance ranking.
I think both Google Uncle Sam and FirstGov. are good. If I had to pick one that I would use on a daily basis it would be FirstGov.gov.