Earlier quoted context omitted.
I tend to rate Mary Shelley as the earliest sci-fi author. Not just for 'Frankenstein', but also for 'The Last Man'. I would strongly recommend tackling Issac Asimov's 'Foundation' series as one of the all time classics. Another pretty early one to take a look at is 'We' by Yevgeny Zamyatin. It was the first book banned by the USSR and was the inspiration for Orwell's 1984.
The Foundation series is certainly on my list. I have been giving series lower priority, simply because I want to go breadth-first, but I'm not confident this is a reasonable strategy, especially since I could just read the first entry and decide from there how to proceed. I had not heard of We, but I will look into it.
Asimov: The Gods Themselves
Clarke: Childhood's End, Rendezvous with Rama
Herbert: Dune, Whipping Star
Bradbury: Fahrenheit 451
Bester: The Demolished Man, The Stars My Destination (also called "Tiger, Tiger")
Niven: Ringworld
Niven and Pournelle: The Mote in God's Eye, Footfall
Gibson: Neuromancer
Stephenson: Snow Crash, The Diamond Age
Bear: The Forge of God, Eon
Sagan: Contact
van Vogt: The Voyage of the Space Beagle
Lem: Solaris
Atwood: The Handmaid's Tale
LeGuin: The Left Hand of Darkness
Lewis: Out of the Silent Planet
Some of these are the beginnings of series or have sequels, or exist in a larger continuum of stories. But each can be read and appreciated on their own. If you find one you really like, it's not hard to see if there are more in a series or sequel.Edit: formatting