Gotta be Floyd!
Of course Floyd often comes up in a thread like this, but I can state with certainty: Pink Floyd neither did the first psychedelic record nor the first psychedelic cover!
Donovan’s Sunshine Superman came out in 1966:
The OP cites the third Byrds album, but their first album cover, from 1965, is arguably kind of psychedelic; it’s a group shot of the band, but just slightly distorted in a way that I hear may resemble the visual illusions produced by LSD.
Rubber Soul is a lot trippier and came out right about the same time, though, so I think that’s probably the best answer. I’m not aware of any other album covers from 1965 or earlier that are comparably “psychedelic”, however we define that.
(Realizes what he’s done)
Also, The Zombies had some trippy album covers, probably.
I came here to say that. I think TV tropes would call that Older Than Television. I was going to peg it as Older Than Radio, but it turns out radio and Art Nouveau were both invented in 1890.
I see your point, it’s kinda trippy, OTOH it’s just a portrait of the band shot with a fish eye lens, which wasn’t new in 1965.
My dad had all the Beatles’ albums, and he had one called, “Revolver”. I checked, and it came out in 1966.
Yeah, the artwork for “Revolver” was designed by Klaus Voormann, one of the several “fifth Beatles”. They had met him in their Hamburg days, and he later became the bass player for the Plastic Ono Band. I never liked that cover much, it looks kinda amateurish, although Voormann was a studied graphic designer.
Fun fact: Klaus Voormann also was the producer for the band Trio, of “Da Da Da” fame.
With a little Terry Gilliam thrown in.
1950’s pop culture homage to 1920s avant garde
The Jackie Gleason album art actually was by Dali, but as far as I can find, this one from 1949 is not at all a genuine Yves Tanguy
^^
Wow, while this doesn’t look especially like 60s psychedelia, it easily could be a 70s prog rock album cover.
Like the Rush one with the naked guy pointing at the Rene Magritte guy?
I had to look that up, I’m not very much into Rush, the album was “Hemispheres” and yeah, it has a similar aesthetic.
The Beatles Yesterday and Today album originally had the Butcher cover. It had to be covered with a photo of the band.
I still can’t imagine why the band posed for the Butcher photo.
Released in June 1966
Undoubtedly because they knew it would be replaced, making the original album extremely valuable. 
Apparently first state covers (without the pasted-over photo) are selling for over $30,000.
They were getting a little too cute moptop, so they had to do something a little edgy.
Worth noting that a lot of the psychedelic style was influenced by Art Nouveau styles and fonts from the 1890’s.