In my experience from years gone by (say 5-7 years ago), many shared hosting environments required you to ask to have the AllowOverride turned on for a given account (this may have changed, but a few years ago when I was doing sites for people on a lot of different hosting providers, this came up a fair bit).
Now that so many people are just installing Wordpress, I haven't run into that in a very long time and even back when I used to encounter that, I never ran into a host that wouldn't turn it on.
This isn't turned off for security reasons, but for performance. Imagine I have a URL like this
example.com/user/3/images/2010/01/thumbnails/image_tn.jpg
That's not out of the question for a CMS - you can easily end up with something 5-8 levels deep.
Now the server can't know which rules to apply until it recurses up the entire directory structure and finds and reads every .htaccess file. Note, this is true even if there ARE none. So hosts sometimes don't like to turn it on unless someone needs it.
So instead of
Give me example.com/user/3/images/2010/01/thumbnails/image_tn.jpg
The server has to ask
-does example.com/user/3/images/2010/01/thumbnails/.htaccess exist? If so read it and remember its rules
-does example.com/user/3/images/2010/01/.htaccess exist? If so read it and remember its rules
-does example.com/user/3/images/2010/.htaccess exist? If so read it and remember its rules
-does example.com/user/3/images/.htaccess exist? If so read it and remember its rules
-does example.com/user/3/.htaccess exist? If so read it and remember its rules
-does example.com/user/.htaccess exist? If so read it and remember its rules
-does example.com/user/.htaccess exist? If so read it and remember its rules
-does example.com/.htaccess exist? If so read it and remember its rules
- okay, let me process all those rules
- hmmm... none apply
- Give me example.com/user/3/images/2010/01/thumbnails/image_tn.jpg
Now think of the 250 sites typically sitting on a shared server. As a hosting company do you want to do this for the 25 that need it? Do you want to do this for the 200 that need it?
I think these days, it's more likely for 100 or more sites on the server to need it, so at that point, it costs more in support tickets than they save in hardware.