(Re-posting comment since edit doesn't seem to work?)
I'm 23, and I graduated from Computer Science in 2012. I worked 8 months at a subsidiary for a FTSE 100 company, then I left and joined a much smaller company. Through that move, I gained an opportunity to work in Asia, which I took, and I've been here for almost 12 months now. I love every single minute of it. Rather than try to advise you on decisions I've only recently made myself, I'll offer a brief overview of my time at each company:
Startups/small companies in general are different (I did several bits of work between school and leaving University, my two jobs listed above are only "salaried" experience, not all my experience). Things are "fast and loose" - I read that somewhere, but it's true. I've had decisions made one day turned over the next, and this really screws with the development process. They're fun places to be, with people motivated and passionate about the company vision, and every opinion counts in a small company.
Larger companies let you learn things. I learned so much from my time at a large company, I'm still figuring some of it out. At least half of my marketable skill-set came from those 8 months. When I left University, I'd written a single implementation of Boids in JavaScript. Now I am employed full time as a Front-End JavaScript developer in a foreign country. Larger companies can still be fun places to be, but they're a lot more robust. Things change slowly, and this can be frustrating. But they also use some awesome tech, and they can be an excellent place to "skill up".
With regards to other comments:
If a startup fails, you are not going to be thoroughly screwed unless you had a primary role in screwing it up - you took a risk, you took initiative and you will have had significant input on the company's product or solution - employers will value that
The comments about getting used to benefits and a big pay-check are true - a variety of factors caused to me to move companies, and I took one hell of a pay-cut doing it - that's not an easy thing to adjust to
Great managers are a must. If you go for an interview anywhere, ask to meet your supervisor, or whoever you'll be reporting to most of the time. I learn as much from my managers as my colleagues.
Talk of larger companies exposing you to other large companies and brands is true, but at the same time we are a company of Sometimes I think I should have chosen the smaller company first. However, I realise that I only think that because I have the experience of a larger company to draw upon. If I did choose the smaller company first? I imagine I'd sometimes think I should have chosen the larger company instead :P
One final comment: I'm originally from the UK, and we don't have anything like the Valley, despite what various MPs and Ministers would like to believe. San Francisco is not a requirement for life in a startup, and I've never understood the glamour associated with it - maybe that's because I've never been so I don't know what I'm missing, but I'm perfectly happy here :)