1. I really do not have too much stomach for “cutesy”, I must confess.
2. Reading subtitles would degrade the experience too far.
3. I would prefer something suspenseful or mysterious, but note that I have no taste for horror—I spend too much time alone with my imagination for that!
4. Well-dressed people are not a requirement but a boon. That would be “well-dressed” by my eccentric standards—good hats, frock coats, spectacles, boots, and the like. I suppose it is a rather strange thing to add, but I have not too much else.
5. Anything cerebral would please me—something that might give my mind something to chew.
This probably is a naïve, vacuous list, but I know nothing of anime, and I rarely watch any kind of entertainment at all, so it is hard to speak of my tastes. I chose this anime topic because I think I would like to watch something in addition to the occasional The Twilight Zone episode, and this seemed as good a place to start as any.
As has been mentioned before, Death Note. You can check off suspenseful and cerebral -- and the dub is pretty good. It's certainly not cutesy. It plays out much like a game of cat and mouse -- a genius detective trying to catch a killer who commits his crimes with a supernatural tool. It was what got me into anime, and what I gave to my friends to get them into it, as well. I honestly haven't watched it in years, so I have no idea how much I'd like it today (I'm sure my tastes have changed significantly) but it's certainly worth a shot. If you watch the first couple of episodes and aren't hooked, then maybe consider moving on to something else.
I'd probably recommend not watching Gurren Lagann right away, as it succumbs to some serious anime tropes that could turn off a newcomer. I'm looking at you, Yoko.
Baccano! is a great suggestion, though -- it manages to be funny, suspenseful, and (at times) hotblooded. I don't have experience with the dub, though.
If you want choices, there's Yume Miru Kusuri, but YMMV with it.
I seem to remember really enjoying Yume Miru Kusuri (with the exception of the student council president route) -- it was also the first VN I played that actually had good art, so that might have something to do with it. Word of warning: the story can get a little heavy at times.
quinnr: Clannad is the visual novel I'd recommend -- so long as you aren't going for the true end, it's not ultra-difficult and the heroines are some of the best. I haven't actually cleared it yet -- I stopped midway through to focus my efforts on Fate/Stay Night and wound up forgetting about it after falling into the hole that is the Nasuverse.
Higurashi (and from what I've gathered, Umineko) definitely aren't for everyone, but if you can get past the art and you like mysteries, I'd definitely give them another shot once you have more experience with VNs.
Also, I've heard really great things about Steins;Gate; I loved the anime, so it's next on my list of things to play (after the rest of Higurashi and Umineko...), so maybe it's worth a shot.