Warning: Be prepared for spoilers. This writeup is chock-full of them.
Red Dwarf's genre evolved over time, from sci-fi sitcom to sci-fi action/drama sitcom to sci-fi drama sitcom. Series 4 was where the first noticeable change started to take place. Also, Red Dwarf belonged now to the 23rd century, not the 21st.
Introduced this series were little bits and pieces that would return in later series, such as Kryten's inability to insult, simulants, and Ace Rimmer. Also, a corridor added at the rear of the set was used over and over in Series 4 and 5, being lit differently each time.
On with it, then.
"Camille" was aired on Valentine's Day, 1991. Kryten rescues another mechanoid from a planet about to explode, but when she is introduced to Rimmer and Lister, she changes shape. This was themed on Casablanca, and was used as Lister's teaching aid and the movie that Camille and Kryten went on a date to.
"D.N.A." was also known as Do Not Alter. When the crew find an advanced spacecraft, they explore and find a DNA modifier. When the Cat gets his paws onto it, he turns Kryten into a human. This also had a movie line embedded in it - "How can the same smeg happen to the same guy twice?" - from Die Hard II.
Lister develops space mumps in "Justice", and while he is sick, a pod is brought aboard Red Dwarf, containing either a woman or a simulant. Before the pod thaws, the crew go to Justice World, just in case it is a simulant. But things change when Rimmer is found guilty of manslaughter, and sentenced to 9,000 years imprisonment.
"White Hole" was Hattie Hayridge's episode... sort of. The crew make Holly a genius again, at the cost of reducing her lifespan... to 3.4 minutes. She shuts down, and the ship stops moving. It's back to the primitive life for Lister and the Cat, and Rimmer needs to be shut down some time soon.
"Dimension Jump" introduced Ace Rimmer... what a guy. Ace jumps through dimensions to find our Rimmer, but in the process, makes Starbug crash into an ocean planet. It'll have to be fixed, so Ace sticks his hand up. Ace returned in Series 6 and 7.
"Meltdown" saw the crew creating a teleporter and using it to go down to Waxworld, where war is raging between droids made of wax. Rimmer takes command of one side and helps them through to the end of the war. This episode was considered as the series opener, but was postponed until the end of the Gulf War.
That's it for Series 4. Click here for Series 5... or here if you missed something from 3.