The first album was 100% death/doom. Later they made their sound more and more accessible. More straightforward and even more poppy.
The album "Draconian Times" from 1995 can be seen as their last succesful metal effort before they really became too accessible for some people.
In 1997 things changed radically. With a new look and style, they astounding both fans and critics. On the album "One Second" (1997), the band began to experiment with Depeche Mode-esque synth pop and electronica. Still the band grew. Some older fans were disappointed, but they got more new fans who liked this direction.
From 2007 onwards more metal has become a bigger part of their music again.
If someone wants to check classic Paradise Lost and this person is a metalhead, then (s)he certainly should check out "Gothic",
Gothic is a seminal work, being one of the major influences on the modern genres of doom metal (especially on the doom/death sub-genre) along with albums such as Candlemass' Epicus Doomicus Metallicus and My Dying Bride's Turn Loose the Swans. Of particular note is the use of female vocals, rather unconventional in heavy metal scene at the time.
"Shades of God" (with the ultimate classic "As I Die")
"Icon"
and "Draconian Times".
The debut "Lost Paradise" is very non melodic so more difficult to get into. Still if you're into (or want to get into) death/doom metal, you could check it out. People who are open for less guitar and more electronic music, I'd say check out the rest.