I doubt you can get anything better than Vimeo for delivering your videos, as they're using a content delivery network. If you're getting stutters because of the way they encode it, then that's different.
I'd recommend a decent non-oversold VPS with good amount of bandwidth, and lighttpd or an optimized apache setup.
High Bandwidth Servers
Custom Hosting Solutions
Are you playing them back embedded in a web page, do you need true streaming with full random access to navigate to any part of the timeline, or will progressive download be sufficient? If you're embedding in a web page then I'd avoid true 720/1080 resolution and aim slightly lower as many users won't have sufficient screen resolution to view this, and would end up downscaling the video in the page which is a needless use of cpu. Video stuttering can be caused by bandwidth issues, but also occasionally by cpu use. There's also a balance to be made between bandwidth, cpu and image quality with regards to codec/codec configuration (e.g h.264 baseline versus h.264 main)
For this sort of application I'd generally avoid a VPS due to the fact that multiple VPS accounts on the server will share the servers bandwidth, which can lead to unexpected hiccups if it's being heavily consumed by others.
If progressive download 'streaming' is ok for your use case, then you might want to consider a CDN on a pay per bandwidth/storeage basis, I've had good results using highwinds based CDN's and Amazon Cloudfront for this type of video playback.