Using Hillshade option in ArcMap?
Use Bilinear Interpolation resampling during display
You can somewhat improve the display by changing the resampling method used from the default Nearest Neighbor to Bilinear Interpolation. Layer Properties -> Display Tab -> Resample during display using: Bilinear Interpolation.
This effect works best with DEM and the default black and white color ramp.
You will get a much better result and a lot more control over the display when using 2 raster as you have already done. Make sure you also use the Bilinear Interpolation resampling method during display.
Add DEM:
Toggle "Use Hillshade Effect" on:
Renders as follows on screen:
Change resampling during display to Bilinear Interpolation:
Renders as follows on screen:
Arcmap's on the fly hillshade, the method described, is quick and dirty and was never meant to replace the hillshade result from Spatial Analyst and/or 3D Analyst. Although the same term is used to describe both they are not the same at all.
To create a true hillshade without Spatial Analyst you might try GDAL's gdaldem:
gdaldem hillshade dem.tif shade.tif
The TileMill Terrain Data Tutorial has a nice overview of how to use gdaldem to build a composite hillshade with hypsometric tinting.
If the utility is not direct enough for your application the C++ source code for gdaldem is here.
If you are looking for a good looking hillshade that takes some time to create, but is great for larger projects where it will get a lot of exposure, you might try the Swiss Hillshade Method - it requires 3 layers, but you can then export them to one georeferenced tiff to save space and for portability. This method DOES require Spatial Analyst, I believe, so it is not a direct answer to OP's question, but may be useful to others looking at hillshade methods in ArcGIS. The method works in other GIS systems too, but the linked toolbox is for ArcGIS.
Edit 11/2014: Esri recently released a new tool for creating Hillshades. It look really slick and should fuse with the Asker's workflows. They introduce it here and you can download the code and installation instructions here