32GB Sticks oder kleiner funktionieren in der Regel problemlos.
Den Stick FAT32 formatieren. Damit es kein Chaos gibt kannst du die Musik taggen. Mp3Tag heißt ein opensource Tool mit du es manuell machen kannst, es gibt aber auch noch Software die es automatisch durch eine Datenbank macht. MusicBrainz Picard heißt ist eine gute, die ich auch für meine Musiksammlung nutze.
Solltest du deine Musik als CDs haben, kannst du diese in ein Verlustfreis Format auf dein PC speichern/rippen. Danach in MP3 oder AAC konvertieren. Ich rate zu AAC, da es eine etwas bessere Qualität bei niedrigerer Größe hat.
Ein schneller und günstiger 32GB Stick: http://www.amazon.de/SanDisk-Ultra-USB-Flash-Laufwerk-32GB-130%C2%A...
* Unsere Seite enthält Affiliate-Links, für die unser Forum möglicherweise eine Vergütung bekommt.
Ich hab nen Kingston Data Traveller mit 64GB und Usb 3.0 im Einsatz. Der ist recht kurz von der Bauform her und funzt einwandfrei.
Ich habe den 64GB Sandisk Cruzer Fit im Einsatz. Da passt schon ne Menge drauf. Größer habe ich noch nicht probiert.
Beim erstmaligen Beladen werden die kleinen Sticks ganz schon heiß 
.
Ich würde sogar vielleicht 128 GB Sticks nutzen wollen, hat die schon jemand getestet ob die erkannt werden? Dann kann ich auch noch Hörbücher speichern, die sind in der Regel ja recht groß.
Hat AAC gegenüber MP3 denn Qualitätsvorteile oder sind lediglich die Dateien bei gleicher Bitrate kleiner?
AAC bietet bessere Qualität bei niedrigerer Größe. Größe spielt zwar heutzutage kaum eine Rolle, aber das Navi kann diese schneller auslesen und bei großen Sammlungen kann das schon von Vorteil sein. Das kommt von einem besseren Kompressionsverfahren. Fast jedes Gerät das MP3 unterstütz kann auch AAC abspielen.
Meine Empfehlung
SanDisk Cruzer Blade.
Gibts von 16 bis 64GB
Edited: 
ich enttäusch dich nur ungern aber cruzer blade der is von sandisk, kenn die verbatim produktpalette ganz gut, bedingt dadurch das die firma mein arbeitgeber ist 
und den gibts nur als usb 2.0 variante und is auch als das nicht grad schnell.
128gb oder 256gb hab ich bislang nicht ausprobiert muss ich ma die tage machen, ich wollt auch immernoch ma probieren wie es mit ner externen festplatte aussieht, dann könnt man fat32 bedingt an sich bis zu 2tb als 2.5" platte dran hängen, das sollt für die meisten musiksammlungen mit hörbüchern langen
eine 2.5" HDD von WD hat bei mir funktioniert halte ich aber für Blödsinn da die Platte die Vibrationen / Stöße auf Dauer sicher nicht mag dafür sind die Desktop Platten nicht gemacht; außerdem gibts ja mittlerweile 128GB Sticks das reicht auch für längere Fahrten.
Unterschiede gibt es in der Geschwindigkeit beim lesen darauf würde ich achten, ich habe so einen Mini Stick der braucht einige Sekunden länger bei jedem Start als der vorherige. Außerdem - je mehr drauf ist um so länger dauert das einlesen zu beginn.