Yeah, they are scary as hell, and always seem to appear just when we are initiating an attack on a system >.<

Is there more to AI War than the battles? Is there a story behind it, characters, anything like that?

I never like to see a Dev in trouble but neither game really appeals to me and they are out of my throwaway price range.

No story per se, or characters - at least not in the usual way. But you can make your own story as you go (and believe me, the game can be EPIC), and there many AI types that behave in such an intelligent way that they can become "characters" of sorts, as you play. However, you'll need a bit of imagination to see/enjoy that.
Try the demo, it will give you a good idea of how the game plays, and what it can be. Perhaps you'll like it.

I suggested another distribution channel to them for Tildalis at least (AI War probably wouldn't do well at all via that channel). So we'll see if they're at least successful in finding another outlet for possible revenue too.
I still haven't tried Tildalis, but hearing that you can get versions from several sources just from one key is a nice little incentive to at least give the demo a shot when I have time. Which sadly, won't be for at least a few more days. Darn deadlines.

Question for those who played the AI: is it fun if played singleplayer-only?

Definitely. The multiplayer is purely co-op anyway, with people teaming up against the AI.

YES.
I haven't played it MP, and I hat TONS of fun playing. It scales well, and it's really good.

Aha, thanks for the comments. So it's an insta-buy from my side as soon as I get any sort of cash.

There's a demo available, with substantial content. You can use it to see what's the game like, or to play with a little bit until you have cash to buy it. I strongly recommend it.

One thing I've just realised looking at the Mega Love Indie Bundle is that I don't remember seeing Arcen making much use of the various bundle deals that most other Indie devs seem to throw themselves at with aplomb.

They were in the Indie Strategy Bundle (run by Positech and included Positech's Gratuitous Space Battles and Cryptic Comet's Solium Infernum as well as AI War), but it was fairly unspectacular ($50) compared to, say, Humble Indie.
Although I think they should pull a Introversion and have a bat-shit crazy deal on Steam or something (even through I believe they've explicate said they won't do that.)

Ah yes, I remember that now you mention it. Or rather I remember why I quickly forgot about it. So okay, rather than saying they don't partake in bundle deals I'll simply point out that they're crap at them.

Well I bought $30 worth of games - it's the best I can do for now, since I'm pretty strapped for money.

For anyone trying the demos...once you buy the full game, you can actually just plug your serial key in to the demo and it becomes the full game. Then just continue on with your game.