I ended up signing up for iTunes Match over the weekend and I figured I'd share my experience to anyone who had the same questions I did...
After going through and organizing my collection I came up with about 250 artists and just over 10k songs in total. I signed up for iTunes Match and it did a fantastic job of collecting the metadata, matching available songs, and uploading remaining songs. There were a few small issues with some ineligible songs and duplicates, but nothing major. I'd say it took about 24 hours total to get everything synced up, but I'm sure experiences vary widely here.
Then after double-checking everything I just went ahead and deleted all my files in iTunes. I would click a given set of songs and then tap the delete key. When prompted, I would select NOT to delete from iCloud, but to move the local files to the trash.
After I was finished I had a clean local hard drive and all my music was available for streaming from the cloud... which is precisely what I wanted. When I enabled iTunes Match on my other computer (which had a blank iTunes Music section), it took all of five seconds to sync up perfectly with my collection in the cloud.
So I'm now able to stream music from iTunes on my Macbook Pro and iMac. Those who are looking to stream to iOS might be out of luck, because from what I've seen you have to download the songs from iCloud to your device (although the songs will play as they are downloading... and I suppose there is nothing to stop you from deleting the files afterward).
But this ended up being a perfect solution for me since I primarily use Rdio now anyway. I just wanted to delete the 100GB worth of local mp3 files that were cluttering my local hard drive and iTunes Match helped me to do that and still keep my collection out there in the cloud.
There still isn't a perfect solution in the music technology world just yet, but I can't say enough good things about services like Rdio and iTunes Match. They've worked great for me.