Personally, I learned on Sub Zero, but this was for the PS3 demo when Cage felt a bit too abusable and I didn’t want to build bad habits. I would recommend taking him to training mode to learn execution, but I don’t think I’d recommend playing him as a main if you’re just starting - He’s hard to win with until you get a feel for the game, I think, since he doesn’t really have a set gameplan like a lot of other characters from my experience.
Characters with easier execution, if you want to work your way up to that, would probably be
Scorpion (Though like people said, he doesn’t seem especially good),
Kung Lao (Easy, fun, adaptable, and still very strong even though he’s not the monster he used to be),
Ermac (Easy all around, with high reward, but be careful of relying too much on unsafe special moves)
Raiden (All-around solid, with very good pressure and lots of good strings to mess around with)
Starting characters to avoid IMO
Reptile (Feels a bit clunky and slow until you figure out how he’s supposed to work, relatively execution heavy with mid-combo dashes)
Cyrax (Lots of moves to remember, handles a bit differently from the rest of the cast, very solid otherwise)
Cyber Sub (Same)
Baraka, Sheeva (Don’t bother)
Characters maybe worth looking into?
Kabal (Very good, and has some easy combos, with some complexities you can learn along the way)
Stryker (Easy to play, but maybe a bit limited)
A lot of people seem to like Smoke right out of the gate, too.
I guess like anything else, just screw around until you find someone that matches your style. Just a few recommendations.