Max,
A good vise is the first thing. There are hundreds of styles and types and all come with a range of price tags. For my first vise I would keep it simple. A good cam vise or something like a Thompson AA would be appropriate. The big box outdoor sports stores sell tool kits that have all the necessary hardware including the vise. You can check them out at Cabelas or Bass Pro. Some of the fly shops may also carry the tool kits. I prefer to shop at the local fly shops so you can get a handle on how the tools operate and get good instruction from the store associates.
Next
1. Scissors. Get a good sharp pair styled for fly tying. I like the curved tip.
2. A couple of thread bobbins
3. A small whip finisher or learn to tie a half hitch by hand.
Those are the basics, but there are other sundry items that you will just HAVE to have after you get further involved.
Dano