MySQL queries still slow after deleting bunch of records
Rather than change a pair of tables to InnoDB, it would be better for every table in the database to be converted as InnoDB is a much better storage engine. That said, MyISAM is workable if you don't mind babysitting it every once in a while.
Do I need to clear cache or optimize table in order to see the effects?
⇢ The database engine will clear the cache on its own, but you can force this by restarting the server. Optimising the tables is certainly recommended for MyISAM tables if you haven't done so in a while. This will ensure that the data is in a consistent state and that the indexes are properly linked.
Also I have read that it is better to recreate the table than just optimizing?
⇢ It is sometimes faster to recreate than optimise. If you plan on tackling just the indexes, then DROP and CREATE are your friend. If you want to also check the integrity of the tables, then OPTIMIZE TABLE is what you're looking for. If your site doesn't get too much traffic, you could even look at dropping the index, optimising the table, then recreating the index.
Ideally this should be done for every table in the database, not just the two in question. Databases, like many other things, need the occasional bit of maintenance to remain reliable.