The built in Plex agents that @Lotheric mentiones work pretty well. I believe Plex uses Last.fm by as the default agent for metadata. I have noticed some inaccuracies with metadata provided by Last.fm, so it’s not perfect, although it provides a great appearance and user experience.
If you are looking for more control and perfection in the metadata accuracy, you could apply metadata semi-manually. To do that, you can use MusicBrainz Picard to apply the metadata in bulk. Then you can disable the agent in Plex and just have Plex use only the embedded metadata in the media files.
As a bonus to using MusicBrainz Picard, it will also rename the files according to the Plex recommended file naming convention that you’re asking about. As you save the metadata, Picard will automatically rewrite the file names according to the string format you set… there are many options. In MusicBrainz Picard go to Options --> Options --> File Naming --> Name files like this --> and use a string. I use this string to get the results in the second option you asked about:
$if($ne(%albumartist%,),$num(%tracknumber%,2) - ,)%title%
/Music
/Pink Floyd
/Wish You Were Here
01 - Shine On You Crazy Diamond (Parts I-V).m4a
02 - Welcome to the Machine.mp3
03 - Have a Cigar.mp3
Hope that helps.