Yes, go to Site administration->Users->Permissions->Define roles and edit your Authenticated User role. You'll need to set both moodle/site:viewparticipants and moodle/user:viewdetails to 'Allow'. Have you modified any other permissions? Is your default front page role set to anything? (Home->Front page settings->Edit settings) Can a user who is enrolled in a course view profiles from the 'Participants' link within the course?
The "Profile visible roles" setting doesn't have any bearing on who can view participants or profiles. By default, Teacher, Non-editing teacher, and Student are the "Profile visible roles". This just means that a user who is viewing the participants page will see "All participants", "Teacher", "Non-editing teacher", and "Student" choices in the drop-down selector at the top of the page.
Edit: Sorry, I just re-read your original post more carefully, and I think I see the issue. You'll want to set the moodle/user:viewdetails (Course/View profiles) capability to allow, rather than moodle/user:viewalldetails (User/View user full information).