My first personal vps was the AlienLayer 192MB plan, like several other people here. It was one of the earliest really cheap plans, cheap enough that I could buy it for experimentation without having an actual use for it. I was very happy with it even though it was horribly unreliable by current standards. I got my money's worth ($15/year or so, when everything else cost much more) just from the experience of setting it up and installing some stuff on it and serving a few personal pages.
Before that I used a Rackspace VPS for some work stuff, but it had been purchased and set up by one of my co-workers. IIRC it was $12.50 a month for 512MB ram and 20gb of disk or thereabouts. I thought that was very affordable and figured I'd buy one myself once I had a use for it. Then I watched LEB for a while and got the Alien vps and the addiction started.