So.. "Tutaj" and "tu" mean the same?
Yes. It's mostly a matter of stylistics and personal choice.
Apparently the order of the words in this sentence is important. 'nie powinieneś być tutaj' isnt correct... Is this true?
It is correct, but less usual.
I guess it's like "You shouldn't be here, you're needed in another place".