Lowest-Base Palindrome

GolfScript, 20 characters

~:x,2>{x\base.-1%=}?

A different approach with GolfScript other than Dennis'. It avoids the costly explicit loop in favour of a find operator. Try online.

~:x        # interpret and save input to variable x
,2>        # make a candidate list 2 ... x-1 (note x-1 is the maximum possible base)
{          # {}? find the item on which the code block yields true
  x\       # push x under the item under investigation
  base     # perform a base conversion
  .-1%     # make a copy and reverse it
  =        # compare reversed copy and original array
}?         

CJam, 19 bytes / GolfScript, 23 bytes

q~:N;1{)_N\b_W%=!}g

or

~:N;1{).N\base.-1%=!}do

Try it online:

• CJam
• GolfScript

Examples

$ cjam base.cjam <<< 11; echo
10
$ cjam base.cjam <<< 111; echo
6
$ golfscript base.gs <<< 11
10
$ golfscript base.gs <<< 111
6

How it works

q~:N;   # Read the entire input, interpret it and save the result in “N”.
1       # Push 1 (“b”).
{       #
  )     # Increment “b”.
  _N\   # Duplicate “b”, push “N” and swap.
  b     # Push the array of digits of “N” in base “b”.
  _W%   # Duplicate the array and reverse it.
  =!    # Compare the arrays.
}g      # If they're not equal, repeat the loop.

For GolfScript, q~ is ~, _ is ., b is base, W is -1 and g is do.

Mathematica, 67 66 bytes

g[n_]:=For[i=1,1>0,If[(d=n~IntegerDigits~++i)==Reverse@d,Break@i]]

Can't really compete with GolfScript here in terms of code size, but the result for 2³² is basically returned instantly.