Lead female character?
How about this? A female mercenary type chick that gets double crossed at the very beginning (game intro), like almost all GTA lead characters. You used work for some Rogue general or something and the mission goes bad, you get injured, captured sent to prison... couple of months pass, your old comrades bust you out in a kick-ass super action escape scene, (non-playable), then drive you to a safe house, show you where to park your cars and shit.
First playable mission: Contact your old merc pals using phone (you dial in the numbers,or just access the names from a list)... etc..etc...