Phantasy star and PSO are two entirely different boats. Its the same as Metroid and Metroid prime.
As far as the games themselves, I would most definitely start with the 1st game. Any version works too. SMS, GBA, any of the compilations. I would actually recommend one of the compilations cause you end up with all 4 games (#1 requires unlocking on most of them but 2/3/4 are available from the start and usually unlocking the first one only takes 15-20 minutes). SMS version is great but its expensive compared to all the others.
PSO I couldnt stand. Just like Metroid prime, it shouldnt even have the PS name on it. Other people have enjoyed it but, for me, it was painfully slow and boring. Of course I didnt try the online aspect. I tried to play it co-op with my buddy. We ended up walking around in a circle for hours trying to figure out what we could do to advance and nothing. We eventually gave up and never went back.