First thing that comes to mind:
Comment out <a href=https://github.com/mpflaga/Sparkfun-MP3-Player-Shield-Arduino-Library/blob/master/SFEMP3Shield/SFEMP3Shield.cpp#L827>SFEMP3Shield.cpp Line 827</a>
You can see that if the file type is detected as MP3 that getBitRateFromMP3File(fileName); attempts to scan the file for the header to predetermine the bitrate. This is optional and may remove your noticeable delay for larger files.