This is the same problem i suffer with, and i also have large hands (to the point where the 360 controller feels small, and the PS3 controller feels like its going to break), yet 4" + devices just don't feel comfortable to use/hold.
Yeah, if they could make a iPhone 4 size phone with the screen all the way to edges then that's perfect! Anything bigger feels like a tablet!