That's quite an audience to build, and I think that's where a lot of effort goes. It can take a long to time to create and establish a brand and experience that people rely on and trust.
For how difficult it is to "build" such an audience, my guess is don't much try to 'build' it. Instead, if the project is good, then fairly routine publicity, virality, etc. will be sufficient. Otherwise, the project is not very good and need another project.
Generally project selection is really important. For a Web site or app, my guess is that should concentrate on projects that should be of significantly high interest to a major fraction of all Internet users at least in the US and maybe the world. Examples were Plenty of Fish, Hot Mail, YouTube, Yahoo, Google, Apple's iPhone, Google's Android. Sometimes can get a good start with an entering wedge into a niche, but if early on want to get the half million unique users a month, then it should help to be casting the net in an ocean of millions or billions of Internet users.