I doubt you will be able to find an LCD that accepts VGA and is less than $100. And there are no character LCD's I know of that accept VGA -- VGA is meant for truely graphic displays; using it with a character display doesn't make sense.
To make your life easier with the 40x4 LCD, you can get serial versions that just connect to the serial port of the PC. You don't have to mess with connecting all those wires to the parallel port, which can be a real pain if you're not used to that sort of work! There are plugins for WinAmp to drive these serial LCD's. I'm sure if you search the posts on this site you will find links.
Another possiblity which I have myself considered, is using a monochrome graphical display. These are typically 240x64 pixels and are about the same size as a 40x4, only with software you can control all the pixels -- you aren't limited to 40x4 characters. That way you could display graphics such as icons, buttons, VU meters, etc. You may need to have someone write a custom plugin for these types of displays, however.