Stage presence are earned in 'Go On Tour' mode
Stage presence levels are tied to the amount of stars you earn on a show accompanied by the stage presence awards you earn on a show. Legendary seems to be earned when you get the 90 - 100% of the maximum stars available in a show, so if the show is a 2 song show it would be worth 9-10 stars and you'd need to get 5 stars on one of the songs. This happens since you can get presence awards for 5 stars, a long streak on a song, lots of HO POs hit, long time in bass groove, etc which usually go hand in hand with stars earned. Difficulty doesn't appear to matter and the achievement will unlock once the last song has finished.