The Recent Changes page has simplified the filtering UI, and we need to determine where to place the legend. With the new filtering capabilities the legend is less needed for filtering tasks (since filters and highlights allow to focus on the edits of interest without visually scanning the legend keys). Thus, we can consider showing it collapsed initially.
In order to make the best use of space when the legend is expanded, we can show it as a floating element next to the list of results (as opposed to pushing them down). Technically this can be achieved by moving the legend (".mw-changeslist-legend" element) into the list of changes (".mw-changeslist"). You can open the browser console and write the following to see how that would work:
> $(".mw-changeslist-legend").prependTo(".mw-changeslist").css("max-width","250px")
# Mockups
|{F8467020}|{F8467022}|