To change your Pokemon's Tera Type, you first need to beat Gym Leader Larry in Medali. (His Pokemon are around level 35.) After you do, you can go back to the Treasure Eatery where you beat him and ask the chef to change your Pokemon's Tera Type. You can get there fastest by flying to Medali (East).
To change the Tera Type, you will need 50 Tera Shards for the type you want to change to. The main repeatable way to get Tera Shards is from higher-level Tera Raid Battles, which award a few Tera Shards in the same type as the Pokemon you beat.
You can also get Tera Shards as random gifts (for example, the chef gives you 50 Normal Tera Shards for free when you first unlock the feature).
