I went about it the opposite way, and can definitely recommend that as well: big company first, then small. The big company experience shows you a ton of things, like how to interview, build, and deploy at scale. The small company can benefit from your ability to bring order to chaos, develop tools which are obvious in any big company but strangely missing from every small one, and more.
Maybe it doesn't matter which one you start with, but you should give both a try at some point.