Thanks again to CircleDock the Downloader works better.

Introduction 

This article shows how to download YouTube videos using C# code only. The code is very simple to understand and anyone can easily integrate it to in their solution or project.
I didn't use any third party library to do this task. All you need is to take two .cs files and integrate them to your project.

Using the code

There are two main classes in this project:

YouTubeVideoQuality Class

This is the entity that describes the video.
public class YouTubeVideoQuality 
{
    /// <summary>
    /// Gets or Sets the file name
    /// </summary>
    public string VideoTitle { get; set; }
    /// <summary>
    /// Gets or Sets the file extention
    /// </summary>
    public string Extention { get; set; }
    /// <summary>
    /// Gets or Sets the file url
    /// </summary>
    public string DownloadUrl { get; set; }
    /// <summary>
    /// Gets or Sets the youtube video url
    /// </summary>
    public string VideoUrl { get; set; }
    /// <summary>
    /// Gets or Sets the file size
    /// </summary>
    public Size Dimension { get; set; }

    public override string ToString()
    {
        return Extention + " File " + Dimension.Width + 
                           "x" + Dimension.Height;
    }

    public void SetQuality(string Extention, Size Dimension)
    {
        this.Extention = Extention;
        this.Dimension = Dimension;
    }
}

YouTubeDownloader Class

This class downloads YouTube videos:
public class YouTubeDownloader
{
    public static List GetYouTubeVideoUrls(params string[] VideoUrls)
    {
        List urls = new List();
        foreach (var VideoUrl in VideoUrls)
        {
            string html = Helper.DownloadWebPage(VideoUrl);
            string title = GetTitle(html);
            foreach (var videoLink in ExtractUrls(html))
            {
                YouTubeVideoQuality q = new YouTubeVideoQuality();
                q.VideoUrl = VideoUrl;
                q.VideoTitle = title;
                q.DownloadUrl = videoLink + "&title=" + title;
                if (getQuality(q))
                    urls.Add(q);
            }
        }
        return urls;
    }

    private static string GetTitle(string RssDoc)
    {
        string str14 = Helper.GetTxtBtwn(RssDoc, "'VIDEO_TITLE': '", "'", 0);
        if (str14 == "") str14 = Helper.GetTxtBtwn(RssDoc, "\"title\" content=\"", "\"", 0);
        if (str14 == "") str14 = Helper.GetTxtBtwn(RssDoc, "&title=", "&", 0);
        str14 = str14.Replace(@"\", "").Replace("'", "'").Replace(
                "\"", """).Replace("<", "<").Replace(
                ">", ">").Replace("+", " ");
        return str14;
    }


    private static List<string> ExtractUrls(string html)
    {
        html = Uri.UnescapeDataString(Regex.Match(html, "url_encoded_fmt_stream_map=(.+?)&", 
                                      RegexOptions.Singleline).Groups[1].ToString());
        MatchCollection matchs = Regex.Matches(html, 
          "url=(.+?)&quality=(.+?)&fallback_host=(.+?)&type=(.+?)&itag=(.+?),", 
          RegexOptions.Singleline);
        bool firstTry = matchs.Count > 0;
        if (!firstTry)
            matchs = Regex.Matches(html, 
                     "itag=(.+?)&url=(.+?)&type=(.+?)&fallback_host=(.+?)&sig=(.+?)&quality=(.+?),{0,1}", 
                     RegexOptions.Singleline);
        List<string> urls = new List<string>();
        foreach (Match match in matchs)
        {
            if (firstTry)
                urls.Add(Uri.UnescapeDataString(match.Groups[1] + ""));
            else urls.Add(Uri.UnescapeDataString(match.Groups[2] + "") + "&signature=" + match.Groups[5]);
        }
        return urls;
    }

    private static bool getQuality(YouTubeVideoQuality q)
    {
        if (q.DownloadUrl.Contains("itag=5"))
            q.SetQuality("flv", new Size(320, 240));
        else if (q.DownloadUrl.Contains("itag=34"))
            q.SetQuality("flv", new Size(400, 226));
        else if (q.DownloadUrl.Contains("itag=6"))
            q.SetQuality("flv", new Size(480, 360));
        else if (q.DownloadUrl.Contains("itag=35"))
            q.SetQuality("flv", new Size(640, 380));
        else if (q.DownloadUrl.Contains("itag=18"))
            q.SetQuality("mp4", new Size(480, 360));
        else if (q.DownloadUrl.Contains("itag=22"))
            q.SetQuality("mp4", new Size(1280, 720));
        else if (q.DownloadUrl.Contains("itag=37"))
            q.SetQuality("mp4", new Size(1920, 1280));
        else if (q.DownloadUrl.Contains("itag=38"))
            q.SetQuality("mp4", new Size(4096, 72304));
        else return false;
        return true;
    }
}

Points of Interest

Using this code you can select the video quality depending in your internet connection speed to start download.
Many people have slow internet connections and they can not watch videos from YouTube, so I made this code to help those people to download YouTube videos to their PC's so they can watch the videos offline.

Updates

Thanks to Motaz Alnuweiri, the Downloader works again. Added self download videos.