The key is to use the advanced permissions dialog as well as specifying the scope (apply to) of the permission change and also applying a permission set to the CREATOR OWNER of the folder:
First, to give everyone in the group read access to the whole tree:
On the properties of the "Public" folder:
Users: Read & Execute, List Folder Contents, Read
Advanced security tab
Verify the "Users" permission for "Read & execute" has "This folder, subfolders, and files." in the "Apply To" column. Users in this group should have read access to the entire tree.
After that, two access control entries, one for creating folders, and one for granting permission to those folders to the owner:
Add access control entry to allow users to create folders at the top level of "Public"
Name: Users, Apply to: This Folder Only, Permissions: Create folders (Allow)
Add access control entry that gives users full access to only the folders they create under "Public"
Name: CREATOR OWNER, Apply to: Subfolders and files only, Permissions: Full control (Allow)
Edit to add: Be aware that in order for this to work properly with folders that already exist in "Public", you will have to set the owner of those folders to the users who created them if those owner fields have been changed since creation. The CREATOR OWNER permission refers to whoever the owner of a folder is. New folders should automatically be fine.
(XP article but still applies)
Be sure to use the Effective Permissions wizard to verify that things are set up the way you want.