pongu said:
Do I just create random levels and playtest them to see what works?

Yes, i would say.

You can do things like:
Adding power ups, but getting them requires to take a risk of being shoot easily.
Adding water, which slows players down, making them an easy target. Maybe they can't shoot til they get out.
Adding teleporters to make player trajectories less predictive.
(i guess you already have ideas 1 and 3 in some way)

Iirc, the Jump'n'Bump game did some of those things.
I really liked this game. People made custom levels for it, and i've made one too.
You could make it easy to mod, to enable such option.

Visuals look great.
But i would make the dark grey platforms brighter as they are hard to see.