The reason Goto is slow when the Lbl is near the bottom of program is because, IIRC, when the parser encounters a Goto it will search the entire program, beginning to end, until it finds it.
In general, though, yeah, Goto is frowned upon as bad programming practice. Its main advantages are optimizations when you really know what you're doing (or, if in ASM, for example, the language provides no other options.)

I'm not saying that they are bad to use, and if you feel you must use them, go ahead.
No need to scare away new members

I also remember the days when I used to use Goto all the time. I also ended up having to figure out myself what was causing the TI-BASIC “memory” error on the Z80 calcs. What's ironic is that it actually had the reason listed right in my manuals where the error message was explained, but I ignored it because I misunderstood and thought it was wrong—I thought it meant that any time you use Goto in a loop, it would immediately give that error, which of course it doesn't. The fact that it has to be done repeatedly before that happens and the manual didn't make this fact clear caused it to be a long time before I finally figured it out.

This was also around my old DOS QBasic programming days, and I remember causing memory leaks at first by using Gotos in terrible places in my code on that platform, too. Later, I discovered how to add debugging code that would print the amount of memory remaining and was shocked watching it decrease steadily the whole time the program ran. In QBasic, it was rarely a real issue, though, because there's so much more memory available on a PC compared to a calc.

Over time, as I read programming books and experimented with different styles, I gradually used Goto less and less. These days, I pretty much never use it at all—it's become natural for me to write code without using it.

There is just one exception currently—in recent C programs (i.e., TIGCC) I do make very occasional use of Goto when dealing with dynamic memory allocation, which is otherwise a ridiculous pain when it comes time to properly free up that memory (especially on the 68K calcs, where nothing cleans up after you and the memory is lost forever until RAM is reset!). Without Goto, I would have to repeat the cleanup code many times everywhere, wasting space and giving countless opportunities for hard-to-reproduce bugs/memory leaks to hide (and making the code actually harder to read). In this particular case, I think Goto is okay because the alternative is far worse.

So I consider Goto as being kind of like alcohol. There's nothing wrong with it as long as you use it responsibly and don't get carried away.

I wonder if Goto can cause memory leaks on Casio BASIC...

Hmmm...
:0->A
:Lbl 1
:A+1->A
:While 1
:Goto 1

After the error, (total ram available - program size) / A = ~33.

Why does TI need 33 bytes per while?

I rarely use in Basic anymore, but I used to.  Look at my original version of Numb3rs to see how bad it was!  By the time I finished Drifter I was slowly drifting away from Gotos, and Exodus doesn't use any.  Gotos, for me, are only good for putting subroutines inside the main program, like player demonstrated on page 2.

At school, we have to write these basic programs with terribly unoptimized code. 
I know there are situations where the use of Lbl and Goto is inevitable, but all of those programs use the Goto and Lbl commands as like there is no tomorrow.

The programs are so slow that I have a race to see whose optimized code is faster. 

Yes, they try to teach, but most a few see it as an opportunity to play Block Dude.