1) make my sentences more complex (because then I can move clauses around if I find I'm always starting with the same word, and combine several actions into a single sentence)
2) use chronological markers, prepositions and other transition words (when, as, since, before, after, while, then)
3) add in other information, esp. from other characters' actions, or describing things she can senses about the environment (but omitting the "she saw" "she tasted" tags so I get "The air smelled..." or something like that). Remember you don't have to explicitly filter in through the POV character's perceptions.
4) replace a "she" or two with the character's name (but only at well-chosen places, not at random)
5) break up exposition with dialogue and/or omit some of the dialogue tags
Just out of curiosity, I did a quick survey of the sentence starters in one of my current WIPs. Don't know if it'll help or not, but my first few sentences begin with the following words (all before the start of dialogue and interactions with other characters):
Sierra, it, a, she, unless, as, her, if.
quote:
Is starting each sentece with an -ing word just as bad
The short answer is yes. In fact, in my opinion, it's worse.
The problem may not be one of sentence structure, but one of what you are describing. If every sentence starts with "He did/She did," then all you are describing is character actions. I would assume there is a lot more to your story than that. There is setting. Describing the setting will automatically make you start sentences with something other than "He did/She did." There is the meaning of character actions. Like, "This was the first time in seven years Shannon had let herself get close to anybody." Try describing more than just what your characters are doing, and your sentence structure will probably follow suit and vary itself.