I found that I couldn't get into the habit of flossing until I switched to single-use floss-picks. The store brand (rite-aid, whatever) are cheap and thin enough to fit through even my tightest teeth.

I also discovered that, to my astonishment, at some point it stops hurting. It takes maybe 3 weeks to a month and a half, but then the gums are in tough enough shape that brushing and flossing feels more like scratching an itch than scrubbing a sore spot, and it's quite pleasant.