iterate[f1_, f2_, x_, n_] :=
Rest@FoldList[({f1[#1], f2[#1]}[[Mod[#2, 2, 1]]]) &, x, Range[n]];
iterate[Cos[Cos[#]] &, Sin, x, 5]
(* ==> {Cos[Cos[x]], Sin[Cos[Cos[x]]], Cos[Cos[Sin[Cos[Cos[x]]]]], Sin[Cos[Cos[Sin[Cos[Cos[x]]]]]], Cos[Cos[Sin[Cos[Cos[Sin[Cos[Cos[x]]]]]]]]}*)
EDIT: Just learned about ComposeList (thanks J.M.!). Here is a variation using ComposeList and Nest:
iterate2[f1_, steps1_, f2_, steps2_, x_, n_] :=
With[{indices = Mod[Range[n], 2, 1]},
Rest@ComposeList[{Nest[f1, #, steps1] &, Nest[f2, #, steps2] &}[[indices]], x]];
iterate2[Cos, 3, Sin, 2, x, 4]
(* ==> {Cos[Cos[Cos[x]]], Sin[Sin[Cos[Cos[Cos[x]]]]], Cos[Cos[Cos[Sin[Sin[Cos[Cos[Cos[x]]]]]]]], Sin[Sin[Cos[Cos[Cos[Sin[Sin[Cos[Cos[Cos[x]]]]]]]]]]} *)