Since this is a programming challenge, I'll just sketch out the improvements - you'll learn more by solving it yourself.
You could implement this in C, and doing so may be a little faster, but you'll have the same problem just a bit later on. Your asymptotic complexity scales poorly.
When you calculate Fibonacci(n), you recursively call Fibonacci(n-1) and Fibonacci(n-2). Now, both of these are going to call Fibonacci(n-3), so they are duplicating work.
You need to find some way to remember the earlier computations, to avoid calculating the same values over and over again. You could use the technique of memoization, where you store the results in a suitable container. Or, if you're working linearly through the numbers, you just need to remember the last two terms calculated, and discard anything smaller - that can be done with a couple of variables.
If you want to significantly speed the calculation, you should be aware that there's a closed-form expression for F(n) and for n(F) - but that will probably bypass a lot of what you can learn from this problem.