This is how I managed to get it done in Qgis:
Generate the Hillshade using Raster>>Terrain>>Hillshade Analysis.
The Hillshade that was generated in my case, had values from 25 to 190, with values clustered around 150. Using the Histogram, I figured out what would be the values of the 4 classes.
The Hillshade now needs to be reclassified. In Qgis 1.8, there was a plugin called RasterCalc, which has not been updated to QGIS 2.0 API. SO I fired up Qgis 1.8 and reclassified the Hillshade Raster into a new raster with 4 classes.
I used Raster>>Conversion>>Polygonise to convert the raster from step 3 to a polygon shapefile.
Once you have a shapefile, There are several ways of exporting to Illustrator, most of which are lossy.
I created a map in map composer and then exported that to pdf, which I belive can be opened by Illustrator. You can also export to SVG, which could also be used.
Please note, that I wasn't too happy with my polygon output, so I'm not sure how useful this procedure would be.