A good Psychic non-legend in ORAS would be a Ralts. You can decide to evolve it into a the physical sweeper Gallade or the special sweeper Gardevoir. You can't really go wrong here as both has good stats and Mega Evolution. A Ralts can be caught fairly early in the game (Route 102), but may take long as it is rare in that area.
Another good choice might be Abra, which can be caught at levels 10-12 in the Granite Cave. However, like Ralts, it is also rare and might use Teleport to escape. Later on, you can evolve it into a Kadabra and trade it to get a fast special sweeper Alakazam
You may also want to consider Xatu and Wobuffet, which both can be found in the Safari Zone.
Trading over Psychic-type Pokemon, such as Slowbro, can work. You can Mega Evolve Slowbro by first collecting four Shoal salts and four Shoal shells and give it to the man looking for them (in Shoal Cave). He'll then give you the Slowbro Mega Stone.
I'll add more information later...
I hope this helped!
