On Basilisk Station, which I'm reading right now, is in the same category (s.f. with strong female protagonist). The story starts off kinda slow, but is very imaginative and picks up considerably in the last, oh, say, third of the book.
For the benefit of Kindlers, the link is to Amazon, where the book is currently free.