I'm coming to this late (and in the context of getting a legend from Esri services for a Leaflet map), but I think the discrepancy noted between the questioners and the responders is that the "legend" service URL pattern is only available for services coming from ArcGIS Server (Enterprise) instances, but NOT from ArcGIS Online services. It looks like several questioners were referring specifically to AGOL resources...
Also, not every "FeatureServer" hosted in AGOL (at arcgis.com) will have a corresponding "MapServer" REST endpoint, unlike what you see with a standard ArcGIS Server/Enterprise setup.
I'm really hoping that someone else can confirm if this assessment is correct, and that the "legend" service URL pattern is only available for standard ArcGIS Server REST endpoints (for both Feature or Map service layers) and NOT for ArcGIS Online services (of any service type).
If so, and if I still need to support legends for AGOL feature and map resources (not just for ArcGIS Server/Enterprise resources), how do I generate the legend image for use in a web map interface (perhaps using Leaflet, or some other framework)? We're not planning on using any Dojo/JSAPI components...
I the AGOL REST service endpoints, there is a Drawing Info Renderer JSON object with all the necessary ingredients (symbol type, colors, sizes, etc), but it would be nice not to have to roll my own legend generator for AGOL services...