As for Alien Nation, the series was released on DVD from Columbia House (mail order only) and fetches stupidly high prices on eBay:
http://cgi.ebay.co.uk/ws/eBayISAPI.dll?ViewItem&item=6449470696
Good to see it's going to get a decent release now, I wonder how the picture quality will compare...
Some of the Alien Nation tv movies were released on VHS in Australia, "Dark Horizon", "Body and Soul" & "Millennium" at least.