Persona and Waja both C-segment but Persona has a more compact body to be a more sportier car, perhaps thats why you feel its more uncomfortable.
Waja CPS cun mah 
1) Better stay away from this as older Hyundai's are notorious for being fuel guzzlers.
2) It is a decent buy but check if you'll be 2nd, rd or 4th owner. These cars were popular among parents to buy for their kids to go college as a used car was similar in price to a Myvi/Wira back then so they might be at the hands of an accident prone youngster or riceboy wannabe since it is a manual. Something like this would be the top spec. Honda City TypeZ
3) Decent buy and good age, there are alot more to choose from in this price range look for the best condition, youngest and lowest mileage.

2007 Renault Kangoo - there are usually two truths about this car. one is that its very ugly compared to the sleek cars we have nowadays but that ugly boxy shape also gives it great headroom and spacious interior. the second is that conti's are hard to maintain, that is a yes/no answer. Kangoo is pretty popular here as commercial vehicles and also as private cars, can be considered the car that keeps Renault afloat here in Malaysia. So parts isn't an issue but finding an SC might be, perhaps you can poke around your area and see any conti/Renault specialist. Other than that its a good buy.

1997 Toyota Corolla SEG - this is the legendary 20v version, the top spec for this model. Its reliability is unmatched, service parts and maintenance is also cheap. Being a foreman's car you know it can handle being abused but I'm a little wary of cars from these people because they would tamper with things like mileage to get a better price and buying direct from these people would be an adventure, they of course being a car expert would ensure you everything is fine but when you find out later got issues it might be too late.

1998 Honda Accord SV4 - actually there isn't much of a price different between the City and Accord, why not consider an Accord? More spacious, more comfortable, more safe, and also higher prestige. Of course there is a reason why they're around the same price, when it comes to this price range people will look for cheap cars that are cheap to maintain. The Accord although isn't really expensive to maintain, it certainly isn't in the same league as the City so expect maintenance bills around 80-150 for minor and 200-350 for major. Not the RM38 deals you'd expect workshops provide - those are for things like Saga and Kancil 

1997 Honda Civic EK - i think among everything in this price range this the car to buy. The legendary Civic EK. It might not be the firebreathing Type-R monster but the standard 1600cc VTEC is already quite powerful, and if you change your mind and go towards the power modification route there is an endless and limitless option of mods available.

1998 car but mileage only 135K, that means on avg. only used for >5k km per year. That's a bit suspiciously low I'd say, most probably the odo already rewound back a bit. But again depending on the condition, there's a remote chance that it's genuine.

In terms of choice, it depends on your self, are you used to maintaining old used cars or how knowledgeable are you about cars. If you don't know much about cars then probably better get something newer.

So must be non-local?
If you love cars and don't mind to go through a rut of fixing/repairing/restoring an old car then getting those 1990's cars is a good learning for you.
If you have a hectic job and need a reliable car and can't spend too much time at workshops then get a new car like Viva/Myvi.