I find Golbat/Crobat is very useful. The wild ones in the caves later on in the game are around level 40-45, have high speed, and know Mean Look. You can use that then get its HP down gradually.
It's a good idea to use an appropriate PokeBall too:
- Dusk Ball if you play at night, or in a cave. You are 4x more likely to catch it.
- Quick Ball - only good for the very first turn, but works well. If you're using Golbat this means Latios will run if the ball doesn't work, but you can reset and keep trying.
To encounter it in the first instance know that if you cross a route boundary outside then he will move somewhere else. For example between Route 30 and 31.
HOWEVER, if you go to a different route through a building or cave, then latios WON'T move. This is really useful because sometimes they can be a few routes away, but if you can get there through buildings etc you will find them quicker before they go to the other side of the map.