Enable users to view their own profile, without enabling "View user profiles"
You could do this with a custom rule, as follows:

{ "rules_users_view_own_profile_only" : {
    "LABEL" : "Users View Own Profile Only",
    "PLUGIN" : "reaction rule",
    "REQUIRES" : [ "rules" ],
    "ON" : [ "user_view" ],
    "IF" : [
        { "NOT user_has_role" : { "account" : [ "site:current-user" ], "roles" : { "value" : { "3" : "3" } } } },
        { "AND" : [] },
        { "NOT data_is" : { "data" : [ "site:current-user:uid" ], "value" : [ "account:uid" ] } }
    ],
    "DO" : [ { "redirect" : { "url" : "http:\/\/www.yourdomain.com\/denied" } } ]
    }
}


That basically checks to make sure the user isn't an admin or on his own account page before directing to yourdomain.com. If you use the CustomError module, you can redirect to an access denied page.

You might also want to check out the Edit own user account permission module - you might be able to enable that and disable "View user profiles" and get the results you want, although I haven't tried that.