Yes and yes: you can immediately seek wherever you want. If it's the first time a rendition has been watched, and if we haven't chosen to pre-encode the later segments (which we do sometimes), you might see a slightly longer seek time as we create the first segment after seek, but the difference is marginal and goes away on second view.
It's interesting your customers want the video immediately
Yep. Some do, some don't. User-uploaded workflows usually care about this; imagine uploading a video to post to a social network and then waiting 20 minutes for the post to go live. (News and sports care about fast publishing too.) Premium media usually doesn't; if you spend a few hours recording a lecture or a yoga class, you don't care if it takes 10 seconds or 10 minutes to publish.
How long did it take you guys to prove that design out?
You don't want to know. It wasn't easy. The biggest challenge is the ongoing tax; other additions to our transcoding layer have an added degree of complexity. But it's been absolutely worth it for us.