If you have the means to watch zone A blu-rays, it's pretty straightforward to collect the heisei and millennium Godzilla movies, since they all have US releases in fairly cheap two-packs. It used to be a massive pain to collect Godzilla in the 00s, when I had to get releases from the US, Australia, and Hong Kong to have a full DVD collection. Fortunately a lot of old rights issues have been ironed out in the years since.For what it's worth I do not regret buying the criterion set at all. I'll certainly revisit a number of those films (just some more than others). Destroy all Monster would have made for an awesome finale thinking on it really. Godzilla 1954 genuinely holds up and is my favorite behind Shin-Godzilla.
I want to try and find the Heisei era sometime. I think I would enjoy it a lot based on what I hear.
Most of the movies from 1984-2004 range from good to great, IMO. The only real dud in the heisei series is Spacegodzilla. In the millennium series, Megaguirus is mediocre and Final Wars is... divisive (people either love or hate it).
Random millennium-era Godzilla trivia: Godzilla Against Mechagodzilla (2002) and Tokyo SOS have excellent scores by Michiru Oshima, the composer for numerous anime including Fullmetal Alchemist and Le Chevalier D'Eon.