In Aussie, look for some decent 3-piece cranks - maybe try eBay as you will not have the same import fees imposed. Good used Profiles for under $100USD then a new set of pedals.
Flex in cranks is normal though. REALLY! One of the things about steel is that it does have a certain amount of flex to it. It helps to distributed the force of landings through more of the material. Instead of the force being focussed on a single spot, the entire crank takes the force of your landing.
But, there is better grades of steel (4130) and lower grades (mild) that are used, so you want to make sure you have good 1-piece cranks at the very least, with pedals that use a good spindle.