Anyway, ended up playing Settlers of the Stone Age with her, two player. I won 10-8.
It's a good game, actually. Reminds me quite a lot of Starfarers - in that one doesn't annex territory, but instead locations - and there are a lot more of them than in Starfarers, so one doesn't suffer from the problem of having nowhere to go.
It's fixed map, which I wasn't enthralled by, but while I think it would be a problem if played quite as often and frequently as I played Settlers, I can see a game every fortnight for a few months not being a problem. It does have some rearrangeable/randomised elements to it, too.
The best feature is undoubtedly the way you are pushed across the world - there being many incentives to explore/cover territory, in terms of VPs mostly (indeed, it's almost the only way). There's also the fact that as you explore, parts of Africa (where everyone starts - oh yes, the map is a stylised hex-grid world. It's cute, and more importantly, sufficiently stylised that playability isn't noticeable compromised) become barren, no longer giving resources. Those who do the exploring have limited control over which bits. I didn't think I'd like it (and, indeed, was on the receiving end of most of the early deforestation) - but I have to admit, it did rather nicely propel us up and out.
A very nice fix to the usual problem of exponential growth, and uncontrollable momentum, is the cap at 5 settlements, with the change that new ones entail removal of old ones - this combines nicely with the laying waste of Africa (I suspect it is totally barren by the end of a close-fought 4 player game - but I didn't count the relevant tokens). Since you start at three settlements (but no explorers - which are the equivalent of colony ships combined with trade ships in Starfarers) there isn't really any exponential growth to worry about.
Having said that, I was consciously concentrating on developing a long term resources base in the mid-game, while [opponent. I think it's Charon or something] was mostly grabbing VPs. In the late game, this really showed, since I was generally getting lots, and most of what I needed, while she wasn't. Still, it was by no means exponential. Oh, they're down to four resources - and you can now buy a 'move the robber' fairly easily, but at increasing cost, so serious blockading isn't a problem. Having critical African resources permanently removed is, but that's incentive for serious development in Europe, I think.
Turns pass very fast, with resources accumulating fairly slowly (just 5 settlements each, remember - and the spread of good locations is more like Seafarers than Settlers, so a three resource turn is average to good, and no useful resources for two turns is neither uncommon, nor crippling), and actions being pretty few and mostly easy to decide. Certainly our game must have been well over 60 turns each, and took an hour. Trading was minimal, but it always was in two-player Settlers, too.
Anyway, it's good for two, and I'm told it scales well. G&P sell out of it at quite a rate (6 copies since Friday) - but it's worth a look, I think.