PHP was easily one of the first to get some mainstream traction. I was using it in February '96, perhaps earlier. Classic ASP from MS was released in Dec 96, and didn't start making inroads (from my vantage point) until mid '97. I was stuck in '97 doing some odd front page weirdness (htc files? can't recall now) which were extremely limiting. At night, I'd go home and do PHP, and had an ecommerce system (horrible as it was) running on PHP/FI (php v2, essentially) in 1998.
By '97/'98 there were multiple vendors vying in this space - htmlos and ihtml are two names that stick with me, but there are some others I remember but can't recall names. And ColdFusion and whatnot, but... Perl and PHP were the big freebies, even by '97. ASP had speed on its side, but PHP already had convenience and price by '97, and it's gained ever since then. re: Java as server-side web platform - was outside my radar much, but the majority of people I worked with, even Java enthusiasts, didn't give it much credence before '99 - I don't think the infrastructure support was quite settled, and it was too 'wild west' for my colleagues (bunch of other reasons too). (IIRC, CF didn't support user-defined functions for several years, leading to much more difficult to maintain code than it should have been, but... memory gets hazy after 18 years).
But... PHP and Perl were free and largely "good enough" for enough of the problems most people were facing which is why they gained as much foothold as they did. ASP and CF both required a fairly hefty outlay and setup that you generally wouldn't be able to pay for without working in a corporate gig.