I want to start by echoing a few things Sin2beta said. PSO is horrible by itself. I have a buddy who plays co-op games with me and we have tried them all including that one. Its a miserable experience if you dont have online. Also Phantasy Star itself is marvelous compared to the NES version of Final Fantasy. It just goes to show what kind of influence Nintendo had on the gaming world cause if it was simply based on games, you would have many many sequels of PS and almost nothing of FF.
As far as co-op games, I love dungeon crawlers. I have both Baldur's gate games, both Champions of Norrath games, Diablo for the PS1 (which I will not recommend cause its beyond dated), and Dungeons and Dragons heroes for the Xbox. Also Gauntlet Legends was a pretty cool playthrough as well.