You're foolish to turn down a job only if it's a job you really want. No position is so awesome it's perfect for everybody.
Most any job can have interesting problems. That's a function of the problem space, and the freedom you have to explore solutions in it, not the platform/architecture they use.
I've worked at a (very) big company, a (very) small company, and in academia. If you're not sure what you prefer, maybe you should try several (in any order).
There's a lot of "how to write software" that you didn't learn in your CS degree, but you'll pick that up quick enough on any real-world project. I learned most of what I know on a solo project (and reading the c2.com wiki); most people I worked with at the big company still haven't figured it out.
Recent startup people I've talked to have been very interested in my small-company experience (even in a different field), and almost not at all in my big-company experience. Who do you want to impress? If you're thinking of doing a startup, tenure at IBM may not impress potential cofounders; if you want to work on device drivers at Microsoft, a web startup may not be the most relevant.
You will almost certainly have many, many jobs over your lifetime. Even if the one you pick today ends up being terrible for you, it's simply not possible to choose a job so bad from which you can't recover. Not even "Swiss Patent Clerk".