About auto-compiling and performance between Do and Fold

In version 7, after setting the option that Rojo described, your Fold code is nearly an order of magnitude faster than Do:

SetSystemOptions["CatchMachineUnderflow" -> False];

AbsoluteTiming[
 sum = 1.0;
 inc = 1.0;
 Do[inc = inc*Sin[10.5]/i; sum = sum + Tan[inc], {i, 10^6}];
 sum
]

{2.0100028, 0.105747}

AbsoluteTiming@
 Fold[{(#[[1]] Sin[10.5])/(#2 + 1), #[[2]] + Tan[#[[1]]]} &, {Sin[10.5], 1.0}, 
  N@Range[10^6]]

{0.2500003, {0., 0.105747}}

The Fold code can be made faster still with a few optimizations:

sin = Sin[10.5];

AbsoluteTiming[
 Fold[
   {Divide[#[[1]] sin, #2], #[[2]] + Tan[#[[1]]]} &,
   {sin, 1.0}, 
   Range[2, 10^6 + 1]
 ]
]

{0.1600025, {0., 0.105747}}

In this case splitting the operations and vectorizing Tan yields a greater improvement:

AbsoluteTiming[
 1 + Tr @ Tan @ FoldList[Divide[# sin, #2] &, sin, Range[2, 10^6 + 1]]
]

{0.0600001, 0.105747}

This may use additional memory, but trading memory consumption for greater speed is a common programming compromise. If you need to work with longer lists you can split the list into sections and use the output of one Fold as the input for the next:

Fold[
  Fold[{Divide[#[[1]] sin, #2], #[[2]] + Tan[#[[1]]]} &, #, Range[#2, #2 + 10000]] &,
  {sin, 1.0},
  Range[2, 10^7, 10000]
] // AbsoluteTiming

{1.8000025, {0., 0.105747}}

Simple and fast method:

SetSystemOptions["CatchMachineUnderflow" -> False];
inc = 1.0;
a = Sin[10.5];
1 + Sum[Tan[inc *= Divide[a, n]], {n, 10^5}]

It is about 70% faster than your example with Do.

See also: Is there a difference between Divide[a,b] and a/b?