A profile of the horizon plots the apparent elevation of the land-sky demarcation against the direction of view (the "azimuth").
In this plot the "adjusted altitude" measures the angle of view (shown as 1000 times its tangent). It was obtained from a DEM by first computing the viewshed for a 20 meter fire tower at a location near the middle:
This hillshaded DEM has been colored with standard terrain colors (blue=low, browns and grays=high) and masked to the viewshed. The tangent of the view angle can be found by subtracting the tower's altitude from the original DEM and dividing the results by the distance. Here is an unmasked, hillshaded version. The largest changes (relative to the original DEM) occur near the observer location, of course:
The final calculation needs to collect the maximum viewing elevation in all directions. Because we have already computed the distance grid, the viewing directions can be obtained simply by computing its aspect:
These are angles ranging from 0 to 360 degrees. Partition them into discrete ranges of viewing angles. A simple calculation will do: for instance, take the integer part to obtain one-degree ranges. Finally, a zonal maximum (making sure to use only the viewing elevations and aspects as masked to the viewshed) produces a table of the results:
These are the data plotted at the beginning of this answer (adjusted by 180 degrees because the aspect of a distance grid is the reverse of the actual bearing of the point of view).
To recapitulate, the calculations are:
The viewshed itself.
A Euclidean distance grid for the observer location.
A relative elevation (that is, a subtraction) divided by the distance grid to give the viewing elevation.
The aspect of the distance grid.
A discretized version of the aspect grid to create zones.
A zonal summary of the viewing elevation (zones are aspects).
All but the first--which is already available in the question--are fast operations, convenient to perform even on enormous DEMs.
When computing the viewing elevation, you could compensate for the earth's curvature and the refraction of light through the atmosphere by decreasing more distant elevations by a quadratic function of the distance, thereby obtaining a realistic profile of what is actually seen. See "Curvature and Refraction Corrections" in the ArcGIS Spatial Analyst help.