CJam, 10 bytes

{_1.5#\/i}

Try it online by verifying the test cases:

[0 1 2 3 4 8 9 15 16 65535 65536 18446744073709551615]{_1.5#\/i}%N*

How it works

_     " Duplicate integer. ";
1.5#  " Raise to power 1.5. Note that, since 1.5 > 1, this doesn't break the rules. ";
\     " Swap the result with the original integer. ";
/     " Divide. ";
i     " Cast to integer. ";

Golfscript, 17 characters

{).,{.*1$<},,\;(}

I could name my function any way I liked, but I decided not to name it at all. Add two characters to name it, add three to name it and not leave it on the stack, subtract one character if providing a full program is OK.

This abomination runs not in logaritmic time in the value of the input, not in O(sqrt n) time, it takes a whooping linear amount of time to produce the result. It also takes that much space. Absolutely horrendous. But... this is code-golf.

The algorithm is:

n => [0..n].filter(x => x*x < n+1).length - 1

Pyth, 14 characters

DsbR;fgb*TTL'b

Provides a named function, s, which calculates the square root by filtering the list from 0 to n for the square being larger than the input, then prints the last such number. Uses no exponentiation or floats.

Dsb       def s(b):
R;        return last element of
f         filter(lambda T:
gb*TT                     b>=T*T,
L'b                       range(b+1))

Example usage:

python3 pyth.py <<< "DsbR;fgb*TTL'b       \msd[0 1 2 3 4 8 9 15 16 65535 65536"
[0, 1, 1, 1, 2, 2, 3, 3, 4, 255, 256]

Matlab (56) / Octave (55)

It works out the square root by using a fixed point method. It converges in maximal 36 steps (for 2^64-1 as argument) and then checks if it is the lower one of the 'possible' integer roots. As it always uses 36 iterations it has a runtime of O(1) =P

The argument is assumed to be uint64.

Matlab:

function x=q(s)
x=1
for i = 1:36
    x = (x+s/x)/2
end
if x*x>s
    x=x-1
end

Octave:

function x=q(s)
x=1
for i = 1:36
    x = (x+s/x)/2
end
if x*x>s
    x-=1
end

C 97

This should be more or less a straightforward implementation of Heron algorithm. The only quirk is in computing the average avoiding integer overflow: a=(m+n)/2 does not work for biiiig numbers.

uint64_t q(uint64_t x)
{
   uint64_t n=1,a=x,m=0;
   for(;a-m&&a-n;) n=a,m=x/n,a=m/2+n/2+(m&n&1);
   return a;
}

C99 (108 characters)

Here is my own solution in C99, which is adapted from an algorithm in an article on Wikipedia. I'm sure it must be possible to do much better than this in other languages.

Golfed:

uint64_t s(uint64_t n){uint64_t b=1,r=0;while(n/b/4)b*=4;for(;b;b/=4,r/=2)n>=r+b?r+=b,n-=r,r+=b:0;return r;}

Partially golfed:

uint64 uint64_sqrt(uint64 n)
{
  uint64 b = 1, r = 0;
  while (b <= n / 4)
    b *= 4;
  for (; b; b /= 4, r /= 2)
    if (n >= r + b)
      { r += b; n -= r; r+= b; }
  return r;
}

Ungolfed:

uint64_t uint64_sqrt(uint64_t const n)
{
  uint64_t a, b, r;

  for (b = 1; ((b << 2) != 0) && ((b << 2) <= n); b <<= 2)
    ;

  a = n;
  r = 0;
  for (; b != 0; b >>= 2)
  {
    if (a >= r + b)
    {
      a -= r + b;
      r = (r >> 1) + b;
    }
    else
    {
      r >>= 1;
    }
  }

  // Validate that r² <= n < (r+1)², being careful to avoid integer overflow,
  // which would occur in the case where n==2⁶⁴-1, r==2³²-1, and could also
  // occur in the event that r is incorrect.
  assert(n>0? r<=n/r : r==0);  // Safe way of saying r*r <= n
  assert(n/(r+1) < (r+1));     // Safe way of saying n < (r+1)*(r+1)

  return r;
}

Haskell, 28

I believe that this is the shortest entry from any language that wasn't designed for golfing.

s a=head$[x-1|x<-[0..],x*x>a]

It names a function s with parameter a and returns one minus the first number whose square is greater than a. Runs incredibly slowly (O(sqrt n), maybe?).

Haskell, 147 138 134 bytes

Not the shortest code in the world, but it does run in O(log n), and on arbitrary-sized numbers:

h x=x`div`2+x`rem`2
n%(g,s)|g*g<n=(g+s,h s)|g*g>n=(g-s,h s)|0<1=(g,0)
f(x:r@(y:z:w))|x==z=min x y|0<1=f r
s n=fst$f$iterate(n%)(n,h n)

This does a binary search of the range [0..n] to find the best lower approximation to sqrt(n). Here is an ungolfed version:

-- Perform integer division by 2, rounding up
half x = x `div` 2 + x `rem` 2

-- Given a guess and step size, refine the guess by adding 
-- or subtracting the step as needed.  Return the new guess
-- and step size; if we found the square root exactly, set
-- the new step size to 0.
refineGuess n (guess, step)
    | square < n  =  (guess + step, half step)
    | square > n  =  (guess - step, half step)
    | otherwise   =  (guess, 0)
    where square = guess * guess     

-- Begin with the guess sqrt(n) = n and step size (half n),
-- then generate the infinite sequence of refined guesses.
-- 
-- NOTE: The sequence of guesses will do one of two things:
--         - If n has an integral square root m, the guess 
--           sequence will eventually be m,m,m,...
--         - If n does not have an exact integral square root,
--           the guess sequence will eventually alternate
--           L,U,L,U,.. between the integral lower and upper
--           bounds of the true square root.
--        In either case, the sequence will reach periodic
--        behavior in O(log n) iterations.
guesses n = map fst $ iterate (refineGuess n) (n, half n)

-- Find the limiting behavior of the guess sequence and pick out
-- the lower bound (either L or m in the comments above)
isqrt n = min2Cycle (guesses n)
    where min2Cycle (x0:rest@(x1:x2:xs))
            | x0 == x2    =   min x0 x1
            | otherwise   =   min2Cycle rest

Edit: Saved two bytes by replacing the "otherwise" clauses with "0<1" as a shorter version of "True", and a few more by inlining g*g.

Also, if you are happy with O(sqrt(n)) you could simply do

s n=(head$filter((>n).(^2))[0..])-1

for 35 characters, but what fun is that?

Edit 2: I just realized that since pairs are sorted by dictionary order, instead of doing min2Cycle . map fst, I can just do fst . min2Cycle. In the golfed code, that translates to replacing f$map fst with fst$f, saving 4 more bytes.

Perl, 133 characters

Not the shortest by far, but uses a digit-by-digit algorithm to handle any size input, and runs in O(log n) time. Converts freely between numbers-as-strings and numbers-as-numbers. Since the largest possible product is the root-so-far with the square of a single digit, it should be able to take the square root of up to 120-bit or so numbers on a 64-bit system.

sub{($_)=@_;$_="0$_"if(length)%2;$a=$r="";while(/(..)/g){
$a.=$1;$y=$d=0;$a<($z=$_*(20*$r+$_))or$y=$z,$d=$_ for 1..9;$r.=$d;$a-=$y}$r}

Decompressed, that is:

sub {
  my ($n) = @_;
  $n = "0$n" if length($n) % 2; # Make an even number of digits
  my ($carry, $root);
  while ($n =~ /(..)/g) { # Take digits of $n two at a time
    $carry .= $1;         # Add them to the carry
    my ($product, $digit) = (0, 0);
    # Find the largest next digit that won't overflow, using the formula
    # (10x+y)^2 = 100x^2 + 20xy + y^2 or
    # (10x+y)^2 = 100x^2 + y(20x + y)
    for my $trial_digit (1..9) {
      my $trial_product = $trial_digit * (20 * $root + $trial_digit);
      if ($trial_product <= $carry) {
        ($product, $digit) = ($trial_product, $trial_digit);
        last; # Not in the golfed version, but makes things faster.
      } 
    } 
    $root .= $digit;
    $carry -= $product;
  } 
  return $root;
}

Clojure - 51 or 55 bytes

Checks all numbers from n to 0, giving the first one where x^2 <= n. Runtime is O(n - sqrt n)

Unnamed:

(fn[x](first(filter #(<=(* % %)x)(range x -1 -1))))

Named:

(defn f[x](first(filter #(<=(* % %)x)(range x -1 -1))))

Example:

(map (fn[x](first(filter #(<=(* % %)x)(range x -1 -1)))) (range 50))
=> (0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7)

Befunge 93 - 48 Bytes or 38 Characters

101p&02p>02g01g:*`#v_01g1-.@
        ^  p10+1g10<        

Try it over here.

Python (39)

f=lambda n,k=0:k*k>n and k-1or f(n,k+1)

The natural recursive approach. Counts up potential square roots until their square is too high, then goes down by 1. Use Stackless Python if you're worried about exceeding the stack depth.

The and/or idiom is equivalent to the ternary operator as

f=lambda n,k=0:k-1 if k*k>n else f(n,k+1)

Edit: I can instead get 25 chars by exploiting the rule "you may use *, /, +, -, and exponentiation (e.g., ** or ^ if it's a built-in operator in your language of choice, but only exponentiation of powers not less than 1)." (Edit: Apparently Dennis already found and exploited this trick.)

lambda n:n**1.5//max(n,1)

I use the integer division operator // of Python 3 to round down. Unfortunately, I spend a lot of characters for the case n=0 not to give a division by 0 error. If not for it, I could do 18 chars

lambda n:n**1.5//n 

The rules also didn't say the function had to be named (depending how you interpret "You can name your function anything you like."), but if it does, that's two more characters.

Cobra - 62

do(n as uint64)as uint64
    o=n-n
    while o*o<n,o+=1
    return o

Batch - 74

set a=0
:1
set /ab=%a%*%a%
if %b% LSS %1 set /aa=%a%+1&goto 1
echo %a%

C# 64 62

Since this is a code-golf (and I'm terrible with maths), and runtime is merely a suggestion, I've done the naive approach that runs in linear time:

Func<ulong,decimal>f=a=>{var i=0m;while(++i*i<=a);return--i;};

(test on dotnetfiddle)

Of course, it's terribly slow for larger inputs.

C99 (58 characters)

This is an example of an answer I would not consider to be a good one, although it's interesting to me from a code golf point of view because it's so perverse, and I just thought it would be fun to throw into the mix:

Original: 64 characters

uint64_t r(uint64_t n){uint64_t r=1;for(;n/r/r;r++);return r-1;}

The reason this one is terrible is that it runs in O(√n) time rather than O(log(n)) time. (Where n is the input value.)

Edit: 63 characters

Changing the r-1 to --r and abutting it to return:

uint64_t r(uint64_t n){uint64_t r=1;for(;n/r/r;r++);return--r;}

Edit: 62 characters

Moving the loop increment to inside the conditional portion of the loop:

uint64_t r(uint64_t n){uint64_t r=0;for(;n/++r/r;);return--r;}

Edit: 60 characters

Adding a typedef to hide uint64_t (credit to user technosaurus for this suggestion).

typedef uint64_t Z;Z r(Z n){Z r=0;for(;n/++r/r;);return--r;}

Edit: 58 characters

Now requiring second parameter being passed as 0 in invocation of the function, e.g., r(n,0) instead of just r(n). Ok, for the life of me, at this point I can't see how to compress this any further...anyone?

typedef uint64_t Z;Z r(Z n,Z r){for(;n/++r/r;);return--r;}