When is it OK to shrink a Database? I know shrink is the devil: It reverses page order and is responsible for skin cancer, data fragmentation, and global warming.  The list goes on... That being said, say I have a 100 GB database and I delete 50 GB of data -- not on one table, but a general pruning of old data on a database wide level, covering 90% of the tables -- does this constitute an appropriate use case for shrinking the database?

If not, what are the appropriate steps to take to clean house after removing such a high percentage of data from a database?  I can think of two: Rebuild Indexes and Update Stats. What else?
Is the database going to grow again? If so then the effort you're going to put into the shrink operations are just going to be a waste, because when you've got the file size down and then you add more data, the file will just have to grow again, and transactions have to wait for that growth to happen. If you have sub-optimal auto-growth settings and/or a slow drive this growth activity is going to be quite painful.

If you do shrink the database, what are you going to use the freed up disk space for? Again if you are just going to keep that space free in case this database grows again, then you're just spinning your wheels. 

What you might consider doing, now that you've got all this free space in the file, is rebuilding your indexes so that they are better optimized (and it will be much less painful to do this when you have free space to do so - think about trying to change a sweater in a tiny closet vs. a big bedroom). 

So unless this was a major cleanup operation and you really won't be ramping up to the same level of data again, I'd just leave it as is and focus on other areas of optimization.