I think Queen’s “Seven Seas of Rhye” is a catchy tune, although there isn’t really much of a story.
Clockwork Angels - Rush
Cygnus X-1 - Rush
Xanadu - Rush
The great ***Notorious Byrd Brothers ***album features a song called “Space Odyssey.” It’s a musical re-telling of Arthur C. Clarke’s “The Sentinel,” the short story that served as the inspiration for the movie 2001.
Failure’s Another Space Song, off of Fantastic Planet. (IIRC, that’s the only sci-fi-themed song on that sci-fi-titled album, the majority of the rest of the songs being about heroin.)
Uulaa! 
I also liked Klaatu’s “Hope” album.
I hadn’t noticed the “Fantasy” theme as well. Add Wakeman’s Myths and Legends of King Arthur and the Knights of the Round Table.
In the Court of the Crimson King. Whole album, but especially “21st Century Schizoid Man” and the title song.
“Iron Man” by Black Sabbath is a whole SF time-travel short story.
Yes, in a way the whole Ziggy Stardust album is about the end of the world, most explicitly in the opening song, Five Years, although most of the many references to stars on the album are not primarily about the astronomical kind (Starman is an exception) and I do not think the band are really supposed to be actual spiders from Mars.
Also, the song Drive-In Saturday from the Aladdin Sane album appears to be set in in some dystopian future.
On the other hand, his Life on Mars is not science-fictiony at all.
¬¬¬¬¬
And 2,000 Light Years From Home, by The Rolling Stones.
True, but we were asked for stuff that isn’t cringeworthy. (The song is cool musically, but the lyrics do make me cringe.)
I Ran - Flock of Seagulls
Midway through the song, the couple gets beamed up. (“I’m floating in a beam of light with you…”)
She Blinded Me With Science - Thomas Dolby
*
When she’s dancing next to me
I can hear machinery*
Lots of Be-Bop Deluxe, especially the Modern Music suite.
I’d also like to put in a vote for Blows Against the Empire by “Jefferson Starship” (at the time really a supergroup headed by Paul Kantner).
I’m ridiculously biased of course, but I also love Kate Bush’s cover of “Rocket Man.” Besides liking the take on the song, she’s just adorable in the video.
And (seriously, it’s in my DNA, ok?) Hap’s cover of “Space Oddity” always gives me shivers.
Most of her songs fall into the scifi/horror/fantasy realm. Her “100 Years” is about a sentient computer abandoned on a space station. It’s falling apart (which partially explains the repetition of the chorus), but can’t repair itself. It knows what’s happening.
“Phobos” is about the moon.
“Save Our Souls” is a snarky song about the search for aliens (not that she’s against searching, just that while on the one hand some look to an alien race to save us from ourselves, on the other we’ll probably treat them as badly, given the chance, as we’ve treated anyone/thing “not like us”).
“Life On Mars” (not a Bowie cover) is from the POV of a kid who thinks there actually is.
Two I’m not that crazy about but other people I know love them, and who am I to argue?
“Wrong Century” is about time travel.
“Roy (Back From The Offworld)” is based on the film Blade Runner.
There are more but I’ll shut up now.
Yes to the first, no to the second. Wakeman is no Jules Verne, the music was mediocre and the story awful.
For me, Mike Oldfield’s Songs of Distant Earth based on Clarke’s book. Some of the tracks on Tubular Bells II are named after Clarke stories (Sentinel, Sunjammer) but the connection is not clear and I wouldn’t count them.