I'll throw in another vote for Gmail, I've been using it for years and it's quite nice.
Also, you may have keylogger software installed on your computer. It's often a part of malicious software or spyware that basically records every keystroke you make and sends the data to someone, so that might be how they got your password in the first place. If that's the case, then changing your password wouldn't work because the keystrokes to change the password would have been logged as well. Windows has an on-screen keyboard that you might want to use to change your password and log in, as I don't think any actual keystrokes can be recorded that way.