In iTunes, bring up the playlist you use for "all songs" as you say. Click on the album column and you will see it cycle through three different ways of sorting by album - alphabetically by album name, alphabetically by artist then by album, or alphabetically by artist then by year released. Choose either of the second two options to keep all the songs by each artist together on your playlist.
Sync the playlist to your iPhone and play it with the iPod. It will work the way you want. Just remember that the iPod will remember what "playlist" you have queued and will only shuffle/advance for that playlist. For example, if instead of using your playlist, you went to coverflow and chose an album, listened to a few songs, then tried to shuffle, it will only shuffle through the songs on that album.
FWIW, I was new to iTunes when I first got my iPhone too, and I just hated it. I've generally got it working now, however, and it's actually pretty good. Smart playlists are very powerful, so I suggest playing around with them a bit.