I've never done any specific comparisons between VBA and fully-compiled
languages, but I would expect a proper executable would probably run at least 10
times faster  than a semi-compiled language, and 100 times faster than a
fully-interpreted language,

You don't have to go to C++ for full compilation. VB6 will give it to you too,
and you could undoubtedly move your code over to VB with much less pain than to
C++.

OTOH if you go to C++, then its fully object-oriented capabilities might allow a
very different approach to your solution.

As far as running  in another environment but still connecting to the Excel
spreadsheet. Yes you can do it, but you'll then have the overhead of opening
the sheet from the program, and that may also be unacceptable.

500,000 rows by 100 columns is a huge amount of data  to manipulate, and you may
run into performance problems once you start doing too much with it. However,
live with it while you can and get your algorithm thoroughly debugged. The
Excel VBA environment is quite nice to work in - especially if you have two
screens on your computer.

I haven't tried to call externally-compiled computation modules from Excel, but
it should certainly be possible, although cumbersome. Don't worry about it
until you need it.