I generally put the rhythm together first, but then most of my solos grow out of improvising over the rhythm as a vamp anyway... The full story is I'll come up with the chords, then add some fills here and there to make it interesting, and then improvise a solo with the fills / riffs I've used over the rest of it as a pointer... Lyrics I leave to someone else - I'm a cheesemonger there I'm afraid...

You could try some inversions on the chords you're using to escape the cheese maybe?