A bit tricky question generally speaking. I think that I can master the vast majority of songs on Hard but some songs can be real show-stoppers (like Fight Fire with Fire by Metallica and bloody Through the Fire and Flames by DragonForce). I can also 5 star a good number of songs on Expert assuming the songs don't have huge and fast solos or tricky riffs. All these on guitar. As for bass, almost always Expert but again, showstoppers appear (B.Y.O.B. comes to mind.)
As for how to become better, practice makes perfect. If you want some specific tips, I'll give you some.
1) Use your index finger for both the green and red notes. In case you have to press a green/red chord or gree/yellow, use your index and middle finger. Just watch it when songs start throwing triple chords. You esentually have to learn to move your fingers up and down.
Thus index=green, red, middle=yellow, ring=blue, pinky=orange.
2) Practice hammer ons and pull-offs. While they may not have been necessary on Medium, they are definitely on Hard and Expert.
3) When you press two or more buttons, only the highest one counts. So, if you hold green+red together it counts as red and green+red. This can be a useful technique on solos.
4) Learn how to up/down strumming. Some songs can be absolutely ridiculous when it comes to tossing down trails of notes (Knights of Cydonia comes to mind). So unless you want to tire out your right thumb mighty fast, do up/down strumming.
Like I said above, practice makes perfect. Unless you practice the songs, you won't go anywhere. These tips are useful but meaningless without practice. And trust me, Hard is doable. When I first tried I said: "Jesus, how the hell are all the others talking about playing Hard and Expert like it's so easy?" Now, I find songs on Hard to be slow at times.