Analyze what you do.
Write it down. What tempos are you used to? What rhythmic patterns do you use the most? Do you tend to repeat the same intervals?
Take those melodies that made you feel repetitive. Why are they similar?
You will find out exactly what your clichés are. They probably come from your influences. These similar lines come out of you musical mind naturally as you improvise melodies. You obey that musical instincts as a set of rules. This is key.
What you can do:
- Once you find out your rules, break them. Do you use a lot of ascending 3rds? Try a descending 6th for a change. Do you use a short-short-long rhythmic pattern too much? Try long-long-short-long-short.
- Don't just improvise. Write your material. Think of the melody as an entity not entirely dependent of your musical vocabulary.
- Music can always use some math. Particularly when you sing, you can make great use of simple scales and arpeggio study to achieve distinct vocal melodies. That's because singing in small intervals and few notes is so common. Internalize those scales by practicing. With that and some ear training, you will, eventually, internalize more interesting interval, with bigger leaps and a sense of harmony.
Just remember to let your ears be the judge.