I agree that it is a major issue because the current set-up is to encourages the proliferation of global course creators (e.g., see this discussion), and global roles are evil.
Your first proposed solution (adding a Create new course button to the course listing page) would make it somewhat easier for the CC to find the button, but not in all cases. In the worst case, the CC will still need a magic URL
to get to the page with the button. Consider this scenario: front page lists courses and no Courses block
Your second solution is the right one in my opinion. This could be done by adding a Courses link to the Site administration block for Course creators. This would allow course creators to add new courses and new sub-categories within their assigned categories.