BASIC teaches you how to write algorythms without knowing anything about types. Perl is decent for that, although it's a real pain to debug, and completely innappropriate for large programs, like the awful BBS I have to maintain. I don't even know if Perl is available for Amiga.
I'd recommend starting off with plain ANSI C. There's lots of books availabe, it compiles everywhere, and just about any ANSI C book starts you right off with how computers compile programs, treat datatypes properly, and produce modular code, which is nearly impossible in BASIC. Also, ANSI C is a rock-bottom standard, so many books treat you like a beginner and don't bowl you over with technical information. C also has tons of libraries that make jumping into graphics and sound very easy, like SDL and Allegro. They're not very efficient or fast, but you can do cool stuff very quickly. I really wish I hadn't relied so much on AMOS early on.
Most importantly of all, GET A DECENT IDE!!! Notepad and Emacs drive me insane. I need something that color-codes commands, checks syntax, and matches brackets. I use TextPad or EditPlus. Later on, you can move on to a real editor. On the PC, High-end compilers like MS Visual C tend to put a lot of C++ stuff in their IDE, and are wicked expensive. If you're talking about *only* producing code on the Amiga, I have no clue.
There's many reasons C hasn't changed much since it was introduced. It's the language to learn. ;-)