This is a common question, but you're probably missing the point of this tab if you think that all it is for is showing a list of contacts. This is called the contacts home tab, and its purpose is to give you access to your recent contacts and some utilities, such as the import contacts wizard, mass deletion wizard, reports, and more (your features will vary depending on your permissions and organization edition/features).
However, if you're still intent on giving up all this extra functionality for the sake of going directly into a view of all contacts (from the contacts home tab, all contacts is just a click away by clicking on "Go!"), you can override the default page. Just remember, you won't be able to easily access the page at all if you choose to do this.
First, go to Setup > Develop > Pages, and click on "New." Give it a name, and enter the following code:
<apex:page action="/{!$ObjectType.Contact.keyPrefix}" standardController="Contact" recordSetVar="contacts">
</apex:page>
Next, go to Setup > Customize > Contacts > Buttons, Links, and Actions, click "Edit" next to Contacts Tab, and choose your new page.
Now, when you click on the Contacts tab, it will take you to your last list view. Simply choose the "All Contacts" view, and salesforce.com will remember this selection for you. However, you won't be able to click on any standard element to return back to the "home" tab, so you'll lose immediate access to the Tools and Reports quick links.
Per eyescream's request, I'm posting his answer left in the comments above here:
Wait, so you have both overridden Contacts tab and the Custom tab made
out of VF? I don't think you need both. Verify that going to real
contacts tab (/003/o) displays your VF page and if it does - delete
the custom tab?
I've verified this was the issue, and that that his additional suggestion works too, that being:
If you'll ever need an Admin-like backdoor to the original tab - use
link similar to /003/o?nooverride=1
(I keep some of my utility links
in home page component that's visible only for SysAdmins).
Worth noting that I tested the above on non-sysadmin user, and the user is able to view the default page if they know the parameters to pass in the URL; which makes sense.
Best Answer
You can change default tab by app level. You need to go and edit apps which you need contact as default tab. Go to Setup > Create > Apps. Choose app do you need to modify. Select contacts as default landing tab and enable profiles which need this setting.