Depends on the company. We always suggest they talk to Techcrunch, since Techcrunch covers all types of startups. Beyond that it depends on what they're doing and how much money they have. PR firms are good for startups that have raised at least a million; I wouldn't use one with much less. Google ads are good if you're doing something very specific. I wouldn't recommend email as a way of getting new users. The white hat half of SEO should be done as a matter of course; and the black hat probably never.
On the whole, the best ways to get attention are the honest ones: to make something so good that people spontaneously tell their friends about you, and to impress bloggers so much they want to write about you. This is especially true for YC cos, because we like to fund people whose strength is in building things, rather than marketing them.
It took me a while to realise this. I looked at all the software on my PC that I use, and I realise, almost all were recommended by either my brother or my friend Joe. If he discovers anything new and nice, he'll call me and tell me, because we're both computer fellas.
I will then tell a few of my contacts, and in a single day, the software joe recommended could easily reach 20 people. On the second day, those 20 people will probably spread it further.
Good software needs seed marketing. You need to get the news out initially, after that people will recommend it. What one should do is add features or design around a philosophy that makes personal recommendations easy.
Marketing is not neccessary if you design with marketing in mind. If your app does not get recommended it's because you've not reached your goal yet.
You're not cool enough for Joe to call me and say - hey Max, check out what I just found...
On the whole, the best ways to get attention are the honest ones: to make something so good that people spontaneously tell their friends about you, and to impress bloggers so much they want to write about you. This is especially true for YC cos, because we like to fund people whose strength is in building things, rather than marketing them.