Re-designing a Database cost and advice
Generally speaking when you want to fix a big-ball-of-mud architecture it is best to focus on one small aspect that you can fix relatively quickly with maximum payoff. What that thing is will vary depending on the system. Once you identify that thing then implement it and look for an opportunity to fix something else.  Over time your big-ball-of-mud will get more and more under control.  This is assuming that the rest of the team is on board with fixing the mess you're in.  If they aren't committed to moving away from the status quo then you'll be fighting a battle you can't hope to win.
Adding a few indexes seems like a quick and easy win, so that will probably be a good place to start, but YMMV.
In parting keep in mind what Warren P mentioned in a comment:

A mess that was made over several years is seldom less than several years work to clean up.

You and the rest of the team need to be committed to this clean-up over the long term if there is any hope for success.

Responses to OP's comments:

Wouldn't it be better to start with database normalization? I mean in a development environment, in order to end up with a fully structured database? There are like 6 tables which HAVE TO be separated, in order to be more &quot;elastic&quot; for future requests.

Normalization is likely to touch many queries/statements across the system. That is a very intrusive change that will take lots of time and effort to show a benefit. Making small incremental steps will be easier, quicker, and steadily improve your life. Before considering normalizing I would move all data access into stored procedures. That will give you tangible benefits quickly, allow you to spread out the work, and make the normalization step easier.

[T]he entire team is ready, and we are talking about a 6 month - 9 month project of restructuring everything, the big bosses are still undecided however.

Read this post by Joel Spolsky before advocating stopping everything and pursuing the grand redesign. Blocking updates to the existing system while you restructure the old system over the next 6 to 9 months makes it hard for the business to succeed. Supporting the current product while concurrently improving the same code base is the smartest play IMO (in my opinion). In this way the code base improvements will just be a symbiotic extension of supporting the current product.
Note: I'm not suggesting you have one team doing a rewrite (version 2.0) while another is supporting the current system (version 1.x).