Its really important that you understand the OWD in Salesforce properly. Since you have set the OWD of object to 'Public' it means that any User, be it User1, User2, User3...UserN, will be able to see records created by any other User.
While setting the baseline, here are the 3 question that you should ask
- Who is the most restricted User?
- Should he be able to see all records? No - PRIVATE; Yes - Next Question
- Should he be able to modify all records? No - PUBLIC READONLY, Yes - PUBLIC Read/Write
Also please note that sharing rules are used to expand the baseline OWD and not limit them. In your case OWD for corresponding Object should be Private as Answer to Q2 goes NO.
Some Links for reference :
https://help.salesforce.com/HTViewHelpDoc?id=managing_the_sharing_model.htm&language=en_US
http://www.shellblack.com/administration/owds/
http://www.crmsalesforcetraining.com/organization-wide-default-in-salesforce-owd-settings-in-sfdc/