1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

für jeden Monat von ... bis
  prüfe die ersten Tage von ... bis
    handelt es sich um einen Dienstag?
    ja => in Zwischenspeicher eintragen, 
          dann Abbruch in diesem Monat, weiter mit dem nächsten Monat
    nein => nächsten Tag prüfen
  Ende
Ende
//  Ausgabe des Zwischenspeichers
für jeden Monat von ... bis
  Schreibe eine Zeile mit dem Inhalt des Zwischenspeichers                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:

using System;
using System.Collections.Generic;
using System.Text;

namespace DateTimeTester
{
    class Program
    {

        static void Main(string[] args)
        {
            string[] myArr = new string[20];

            Console.Write("Geben Sie das Startdatum ");
            Console.Write("im Format tt.mm.jjjj ein:  ");
            string strDate = Convert.ToString(Console.ReadLine());
            strDate = strDate.Replace('.', '/');
            DateTime newDate = Convert.ToDateTime(strDate);


            Console.Write("Geben Sie das Enddatum ");
            Console.Write("im Format tt.mm.jjjj ein:  ");
            string endDate = Convert.ToString(Console.ReadLine());
            endDate = endDate.Replace('.', '/');
            DateTime lastDate = Convert.ToDateTime(endDate);

            int start = newDate.Month;
            int ende = lastDate.Month;

            for (int Monate = start; Monate < ende; Monate++)
            {
                int x = DateTime.DaysInMonth(newDate.Year, Monate);

                for (int y = 1; y <= x; y++)
                {
                    DateTime g = new DateTime(newDate.Year, Monate, y);
                    if (g.DayOfWeek.ToString() == "Tuesday")
                    {
                        myArr[Monate] = g.ToLongDateString();
                    }
                }
                
            }
            foreach (string tag in myArr)
            {
                Console.ForegroundColor = ConsoleColor.Blue;
                Console.WriteLine(tag);
            }
            Console.ReadLine();
        }
    }
}                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:

List<DateTime> myArr = new List<DateTime>();

Console.Write("Geben Sie das Startdatum ");
Console.Write("im Format tt.mm.jjjj ein:  ");
string strDate = Console.ReadLine();
IFormatProvider culture = new CultureInfo("de-DE");
DateTime firstDate = DateTime.ParseExact(strDate, "d", culture);

Console.Write("Geben Sie das Enddatum ");
Console.Write("im Format tt.mm.jjjj ein:  ");
string endDate = Console.ReadLine();
DateTime lastDate = DateTime.ParseExact(endDate, "d", culture);

int start = firstDate.Month;
int end = lastDate.Month;
DateTime currentDate;
//  für die Aufgabenstellung wäre start=1 / ende=12 ausreichend,
//  aber das ist eine sinnvolle Erweiterung und Verallgemeinerung;
for (int month = start; month < ende; month++)   {
    //  auf meine Idee zur Optimierung als Ersatz für die folgende
    //  Schleife verzichte ich jetzt
    for (int y = 1; y <= 7; y++)       {
        //  hier hast Du die Verallgemeinerung nicht beachtet; du setzt
        //  voraus, dass das Jahr einheitlich bleibt
        currentDate = new DateTime(newDate.Year, month, y);
        if (currentDate.DayOfWeek == DayOfWeek.Tuesday)   {
            myArr.Add(currentDate);
            //  ein weiteres Datum kann es in der inneren Schleife nicht mehr geben
            break;
        }
    }
}                
//  Ausgabe
Console.ForegroundColor = ConsoleColor.Blue;
foreach(DateTime day in myArr)   {
    //  hier spielt das Ausgabeformat eine Rolle
    Console.WriteLine(day.ToLongDateString());
}
//  anstelle von Enter genügt die Eingabe eines Zeichens
Console.ReadKey();