Audio players that access music library as file browser (and see folder structure)
First, an example is Foobar2000 in Wine. Foobar2000 has different ways of displaying media library, my favorites being Album list (foo_albumlist, component installed by default) and especially Facets (foo_facets, component to be manually installed). I am aware that finding something better than Foobar2000 is unlikely. The downside of Foobar is of course using Wine.
DeadBeef has a plugin called File Browser that displays the media library as folder structure. You need to select the path to the library: Edit-Preferences-Plugins-File browser-Configure. Only one such path can be set, which is a limitation.
Deadbeef player has playlist tabs but no library search (as far as I know).
Clementine is an excellent player. You just have to select "Files" instead of "Library". The player has playlist tabs.
sudo apt-get install clementine
Qmmp, mostly known fot its winamp-like GUI, has plugins (qmmp-plugin-pack) and one of them can activate a GUI which has the features demanded here.
sudo add-apt-repository ppa:forkotov02/ppa
sudo apt-get update
sudo apt-get install qmmp qmmp-plugin-pack
Amarok. Just like in Clementine, file browsing is available by selection on a left pane.
Thereon, it operates much the same way, except there are no tabbed playlists. These are accessible from a separate left-pane, Playlists > Saved playlists; they cannot be created from within the file browser. To create one, the easy way is to create a current playlist, go to Playlists as indicated (Playlists > Saved playlists), select the current playlist content and dra&drop it among the saved playlists.
Yarok can also access folders as intended here. No real tab playlists,but playlists are easy to create and access.
sudo apt-get install yarok
Quod Libet. Choose View - File System, then select one or multiple media library folders (Music-Preferences-Library);these folders are then displayed along the /home folder and mounted partitions and external drives. They can be browsed, but there is no context menu nor drag-and-drop for folders: to get files into the current playlist one has to browse down to the audio files. Only then, these can be selected and added to a dedicated playlist. Access to playlists is by going again to View-Playlists; there is no common/parallel display of File browser and playlists, and playlists content is accessible only when selected (no parallel playlists like in tabs)
For KDE - Kaffeine - the KDE media player. I was pleasantly surprised how thoroughly this player is satisfying the demands of my question. In KDE it looks better because it is better integrated with the KDE appearance. In KDE it seems integrated with Dolphin file manager, but it will work very well in other environments and will bring an integrated file manager feature. Without Dolphin some secondary (Dolphin-specific) features, like preview play/view will be disabled, but the most important features are present inside the player, by just selecting the Playlist tab from the left side of the window. In this way it is easy to navigate to the music files and drag and drop them into the playlist.
Pragha can add multiple directories into the library and then accesses it by folder structure. It can display folders with or without the top level by clicking to merge folders or not.
It lacks multiple playlists (like Decibel, and unlike Deadbeef, Clementine, Exaile, Qmmp etc.)
I have tested other players mentioned in the other answers and will try to offer feedback on them too.
Exaile has a GUI that looks very similar to Deadbeef, Qmmp and Clementine and the general experience is similar, given the tabbed playlists.
Guayadeque is a bit different. Its file browser is focused on the different directories added to the library, and that would not access all the system by default, but only the paths set by going to View-Preferences-Collections, and there by selecting and/or creating a collection and adding new paths. This is an advantage, as useless directories are thus not visible. Playlists are accessible by selecting My Music and then the Playlist view.
Decibel is more similar to QuodLibet, in that it has no playlists (tabbed or otherwise). By default, its file browser has a two-option switch between displaying whole folders ("root") or only Home folder, but these can be edited, folders can be added or removed as indicated in the other answer, namely here.
Guayadeque, Deadbeef, QuodLibet, Decibel and Foobar2000 have a folder-view access of the music library (that is a way to select the specific target folders), not just a file browser to access any folders.
On the whole I tend to favor the players that have tabs for playlists and display them in the same window as the file browser, that is: Deadbeef, Clementine, Exaile, Qmmp.
guayadeque 
We made best experience with guayadeque. We can easily switch between library (tag) view and folder view (see also the nice online manual)
For Lubuntu see this screenshot: Guayadeque - Lubuntu 12.10
Try Exaile:
You can update it from a ppa:
sudo apt-add-repository ppa:exaile-devel/ppa
sudo apt-get update && sudo apt-get install exaile
See: Exaile music player lives on, version 3.3.0 released with many improvements [Ubuntu ppa]