Начать безусловно с С. Потом, поняв основные принципы - пробовать себя в ООП, т.е. в С++.
ОС имеет значение только потому, что будут небольшие различия в программах для *nix и windows, но начинать практически все равно где.
Желательно брать при этом не IDE, а текстовый редактор, а компилировать и запускать через консоль. Это немного непривычный способ для работы под виндой, но он точно вас многому научит
А вообще можно поставить на другой диск ubuntu и работать в ней.
