Depending on what you want the songs organized for, you don't need to worry about folders.
First off, any player that can connect to a PC in Mass Storage (MSC) mode will allow you to control how your files are saved in memory. The only possible problem is whether the player will "see" songs that are in subfolders of the main music folder. My first MP3 player was the Sandisk E260, and it saved music to subfolders based on artist, and within those, for album.
That's actually uneccessary because when hooked up in MSC, you can view files and sort them using windows explorer, just as if you were viewing a folder on your HD. It's just not necessary to put them in folders.
When sorting songs on the player - you're on the treadmill and lookin for a song or something by an artistn etc - the logical location of a file (what sub folder of what folder) is even less relevant. Players sort music based on tags for each file - little buits of data telling you the artist,album, genre, etc - for that song.
You can change data by going into properties for that file in windows explorer. But it's a better idea to simply user software like mp3tag (it's free!!!) To organize by tags.
I'd recommend against getting a standalone player - music playing phones make a separate player a pricey redundancy. Your phone (or one you get in the near future) may make your player just a needless expense.
Good luck whatever you choose.