Run Rule once on first login

I did something like this by creating a specific role called 'verified user'. When the a user w/o verified user role logs in the rule takes effect. I was having trouble with endless path redirects so I had to just make a link to their profile page.

Then I have another rule that adds verified user role when specific profile field has some value.

You don't necessarily need Rules for this - Logintoboggan already provides functionality similar to this.

I have used logintoboggan, too. But when I don't need all it's functionality I do something similar with a role to indicate state. During a login event have a rule that checks for an existing role (such as user_has_prev_logged_in). The role does not exist, then assign the user to that role, then redirect the user to the profile information page. The next time the user logs in, that role will exist and the rule will not be triggered to redirect them. I do the same thing sometimes to control a one-time "welcome" message on the screen.