That's not two questions.

1) No. However, you could create an m3u playlist with all of your songs in it and then search that. To do so: load it and then, while in the WPS, hold select to bring up the quickmenu, then pick playlist > search in playlist
2) No. However, as above you can make a playlist with all of your music and shuffle that. Easiest way: if you've got all of your music in folders inside one folder (like say, in the root of the player) you can hold-select that one folder and click insert. For that to work you'll need to enable recursively insert directories in playlist options.)
3) Yes. general settings > playback > auto-change directory