The first published x86 shellcode-style overflow was splitvt, which was announced "officially" just weeks after this tutorial was dated:

http://seclists.org/bugtraq/1995/Dec/2

(My business partner co-authored it).

The first shellcode-style buffer overflow (besides the rtm worm) was Thomas Lopatic's HPUX HTTPd vulnerability from a few months earlier:

http://seclists.org/bugtraq/1995/Feb/109

There was a frantic race to get the first overflow out after 8lgm capped off their run of zero-days with an announcement of a Sendmail 8.6.12 remote that relied on a syslog() overflow (yes, in 1995, syslog(3) had an overflow). I was sitting next to Pieter when he wrote part of the tutorial you linked to. I was pretty young (maybe 19?) but even so, it was a pretty electric time to be involved in security.

(OT) Did you know there's a petition to get mudge to be US Cyberczar? http://www.ipetitions.com/petition/mudge4cyberczar/