I just upgraded to the S4 from a Droid Pro with a tactile keyboard, so the whole touch screen keyboard adjustment was a big concern. I tried Swype for a few days, and then discovered SwiftKey. Would definitely give it a solid thumbs up. Both the swype style (they call it 'flow") of typing is incredibly accurate, and I also found their standard touch-typing keyboard to be very usable also.
They offer a 30 day free trial, after 3 days I just went ahead and paid for it.