This is the steps to modify the Tab Views that first display when you click on the Tab. Mostly people will use the views in the View menu, and favourite them in their browser, but you should edit the Recent Items Views for each object when you set it up.
Recent Views vs Recently Viewed Accounts/Cases/Contacts/Leads Views
The confusion among SFDC admins is that there are actually two Recently Viewed list views - one is visible when you click the object tab (and that one is editable in Setup > Customize > [Object] > Seach Layouts > Edit [Object] Tab Layout), but the second one is visible when you select "Recently Viewed [Object]" from the View dropdown menu. The second one is not editable.
Recent Views (and especially Recently Viewed views), can NOT be modified to show different views to different users. Eg if you have a Partner Community and give them access to their own Accounts or Contacts, then they can see the same fields as internal users (unless of course the field has the security set correctly.
Be careful with this.
Decide on the maximum of 10 columns you want in your Recent Items views for each object
Add that list of columns to your documentation - you will refer to it often. See Views.
Go to Search Layouts for the object you want to change
Click the Edit next to the Tab for that object - eg Contacts Tab
Add the fields you want, and put them in the right order, click Save
If your object has Record Types, be sure to include the Record Type in each view. This will help with Bulk Editing.