There are web based tools for this. Give it a link to the video, it will download then transcode to a format you desire. Then you can download the file from the browser.
I remember using them back in my Blackberry days.
Edit: This isn't the one I used, I can't remember the website anymore. But its something like this.
I'm not sure what you're trying to do - but if you're just trying to download videos to your phone for easy viewing at a later time - i'd encourage you to use MetroTube. You can "preload" a video and watch it later without any data/wifi connection on the MetroTube app. You can choose what quality you want to download in. It'll even tell you the file size.
On phone? myTube and Metrotube are nice YouTube apps which I believe have that function.
On a desktop, I'm partial to DVDVideoSoft's Free Studio programs (just be sure to uncheck the installation junkware) and in the Store, Hyper works well.