How does a foreigner's handwriting look to a native?
It does require a lot of effort. Some Chinese/Taiwanese natives might write worse than non-natives. It all depends on how much time and effort you'd like to put in. First, find the writing you like, and just copy it as many times as it takes for you to write the same thing. It's the same as practice calligraphy really.
As Taiwanese native, we write traditional characters. And I seriously cannot remember how many times I wrote the characters while learning... A LOT for sure XD
Good luck!