1 Good question... Sora wo Kakeru Shoujo definitely satisfies the criteria, but it's not officially licensed in R1. Macross Frontier, ditto. I suppose the next is going to be Black Lagoon, then. Last Exile would be my choice if I did not hate GONZO.

Note that I am discounting non-goofy giant robots, even super robots, but including mecha insomuch they are vehicles (e.g. QT Arms in case of Sorakake are ridiculously cool vehicles, IMHO, but Gurren-Lagann's gunmen are definitely not vehicles).

2 I suggested BGC 2040, but also told her to hold off until we came to a decision, so powered suits are not a negative.

3 How about Dragon Ball Kai? No vehicles; they don't need 'em because they can fly. But plenty of cool explosions, albeit not in every episode.

4 I don't usually make recommendations, but Gunsmith Cats is a 3-ep OVA set in Chicago that's really short and punchy, and it was licensed by ADV and should be available through Netflix, though it might be a little hard to find now that it's out of print. Riding Bean, also set in Chicago and based on a Kenichi Sonoda manga is a good choice, too, and can also be gotten through Netflix. For a longer TV series, I can heartily recommend Baccano!, as licensed by FUNi.

5 Bubblegum Crisis is definitely the choice, although I would go for the original over 2040.  Ghost in the Shell doesn't meet the letter of the requirements but is probably good for the spirit.  And much as I shudder to say it, the current movie remakes of the series not to be recommended are actually quite good and certainly have a lot of amazingly animated 'splody bits.

6 Gunsmith Cats is a great three-ep show; was one of my gateway drugs.

Full Metal Panic is another good one for relative anime newbies. Good mix of humor and bangbang. Outlaw Star is good for many of the same reasons.

If their first show was Popotan, they could do worse than FLCL - it's got a high action-and-weirdness quotient. Abenobashi is up the same alley, but a lot farther; save it for once you're used to the school anime tropes.

Both BGC series will work, though probably "one or the other" is a better idea. The original has better music and a better aesthetic; the TV series has cleaner lines but is a bit more by-the-numbers.

I'd stay away from Ghost in the Shell for the time being. It can get preachy or gaze too long at the ol' navel, though when it's on a roll, it's on a roll. Definitely a good second-wave show when you're already used to the genre and you're in the mood for something with a little weight to it.

Lotta good giant-robot type shows. Stay away from Eva for the time being - again, not a good gateway show. FMP as above, maybe the new Appleseed movies (not the old one, ugly as sin). I liked RahXephon a lot personally, but it's almost a shame to watch it before Eva...

Cowboy Bebop. I know Steven disagrees with me, but I consider it a work of art. And it's quite Western in themes, tones, and designs...

7 Lord Head, Avatar, I thought long and hard about suggesting Gunsmith Cats as I love the show.  The only reason I didn't was because of its age... not having ever Netflix'd before, I have no idea what the likelihood of it being available are.

Bebop... hmmmm... splodey, cool veehickles... hmmmm...

FMP... I dislike the first series, but adore Fumoffu.

Why am I writing this at 547am?  I'm going back to bed.

8 Do you want something on the shorter side? I mean, there's any number of Gundam series, but 26-52 eps is probably too long right of the bat. Same for Macross, even if it's a classic. Now, you could try Gundam: 8th MS Team, or Macross Plus as both are pretty much self-contained storylines. I've heard good things about Black Lagoon too.

I'm also seconding Bebop.

9 Galaxy Angel? Lots of weird vehicles and explosions, but IMHO there isn't anything else to recommend about the series.(Gad, I hated it...)

10 Black Lagoon, probably.  It's very Bruckheimer.

11 Evan.... oh, wait.
..
How's about Madlax?  Noir?  Not so much cool vehicles, but a goodly amount of 'splosions.

12

Explosions and cool vehicles, eh? Strike Witches and Asobi ni Iku Yo would count, I think. Almost every Strike Witches episode features a Neuroi going boom, for example. And the Strikers have to count as "cool vehicles".

Meanwhile, AnIY has a lot of gunfire. Not so many explosions (a few, early) but it has cool vehicles in spades, beginning with Eris's space ship.

13  

we'd prefer anime with more explosions and cool vehicles.

Van Dread was recently re-released in a thin pack (with 2 OAVs grrrr) there is much splodieness and vehicular coollness therein. Both series have very satisfying climaxes.

I am not generally a fan of Gundam per se, the series are too long and depressing, but there is a short OAV series from '91 called 0083 STARDUST MEMORY that is quite good. The mechs are McGuffins, but not the focus of the writing. The hunt For Red October + the Battle of River Platte plus The Riechstag fire in space. Recently re-released, it holds up surprisingly well .

I agree with most of the things said, re: BGC. It is quite good.

 Black Lagoon  does get painfully grim towards the end of second season...but there is OH so much splody goodness.

Cowboy Beebop is good if one hides the last two episodes, though it such a Quinn Martin production that its retro elements might be a turn off to your friends.

 Last Exile is gorgeous steampunk though it tries so hard to be epic that it just comes off as pompous at times. Still it has good characters and really cool vehicles that go 'splody in a most pretty way.

14 I can't see recommending Strike Witches to a new fan. Not that I'm saying it's a lousy show, but well... I mean... no pants. It's the same reason I wouldn't recommend Divergence Eve - there might be a good show under there, but that's NOT the first thing you're going to think of!

Noir isn't a boom-boom things-blowing-up show, really. Even so, it might well do the job...

15 How about "UFO Princess Valkyrie 2"? In terms of "cool vehicles" there's Mehm's space ship. In terms of explosions, some of the battles between Valkyrie Ghost and Akidra are legend-making. (Don't look at me like that. I'm no loon.)

Actually, I think the suggestion above of Vandread is a pretty good idea. And I just thought I'd point out that Martian Successor Nadesico is back in print.

Another possibility is "Burst Angel". I didn't happen to like it, but that doesn't mean it's worthless. (It just didn't fit my taste profile.)

16 Av, thank you for pointing out the whole "new fan" thing!  Remember folks, all these two have seen EVER is the first episode of Popotan.

17 I agree with the earlier suggestions.  However, for a newbie, perhaps something that tells a complete story in one sitting, rather than a long series?  I suggest the Cowboy Bebop movie to start.  If they like that, then mention that there's a full season series which shows how the characters met, back stories, etc.

18 Brickmuppet nailed it, with the exception of Vandread/Stellvia twins. Those have too much else going on.

19 Nadesico was another of my first anime. Watched it with the club, along with Fushigi Yuugi... It's good but also a lot better once you've got some nostalgia going on. ;p

20 OK, now to be serious:

How about "Crest of the Stars"? You got your cool vehicles and explosions in spades. And it's an example of good anime, with good characters and a good story and little or no pandering.

21 I can't think Crest is a good starter.  For people that have watched one episode and want more, with big booms, there is no reason to go further than Vandread and BGC to start with.  I still recommend the original BGC.  It's got good art, amazing music, and a story that works if you don't spend too much thought on it but has layers to unravel if you want to think about them. It also is in OAV format, so you don't have to wait for episode 13 or 26 to conclude something.  If they like that, then you can hit them with Vandread, and then think about branching away from 'splody stuff as the focus and get out the Ghibli, Haibane, etc.