#Style

Aside of @syb0rg's answer, there are some comments in the text intended to describe the method that follows. These should be docstrings instead.

You also happen to have magic numbers and sequences that would be better as constants, at least class-level attributes:

class Simon:
    IDLE = ("red", "blue", "green", "yellow")
    TINTED = ("#ff4d4d", "#4d4dff", "#4dff4d", "#ffff4d")

    FLASH_ON = 1000
    FLASH_OFF = 250

    def __init__(self):
        ...

#Reinventing the wheel

Instead of drawing rectangles on a canvas and binding events to them, tkinter provides the Button widget which allows a lot out-of-the-box: changing the color is done with button.config(background='green'), binding an action is done with the command attribute; and you can also disable a button so user can't interact when the sequence is being displayed.

The only thing to take care of, is retrieving the right button into check_choice: you'll need to add some kind of index parameter. But the command keyword used when building a button expects a no-arguments callable. You can overcome that by using helper methods that call check_choice with a fixed index, using a lambda, or using functools.partial.

#Flashing the tiles

I find the way you handle showing the sequence to the player somewhat uncommon. Having flash being called twice (on + off) between two calls of show_sequence feels weird. It would be more straightforward to have show_sequence initiate stuff and then a flash_on and a flash_off method that are calling each other using self.master.after (and using the self.FLASH_ON and self.FLASH_OFF constants).

#Iterating over the sequence

Not that your way of doing is that bad considering the constraints, but I just want to show an alternative approach: using iter and next. Instead of storing the current index, you store an iterator to you sequence using iter and the current button that should be pushed. After a successful button push, you update the current value using next and if StopIteration is raised, then it means the played reached the end of the sequence.

This method can be used both when waiting for user input and when flashing the buttons.

#Nitpicks

I find that flashing a tile for a whole second is a little bit slow. I personally would have used 600 or 750 ms.

I also find that the tinted colors are too close to the idle ones (except for green). You should use colors that are more distinct so the player can better see which one is next in the sequence.

Lastly, I feed that running self.master.mainloop() or even having the root created outside the class does not allow for much customization, I would keep things internal and provide a method to launch the game (that will run self.master.mainloop().

#Proposed improvements

import tkinter as tk
import random
from functools import partial


class Simon:
    IDLE = ('red', 'blue', 'green', 'yellow')
    TINTED = ('#ff4d4d', '#4d4dff', '#4dff4d', '#ffff4d')

    FLASH_ON = 750  #ms
    FLASH_OFF = 250  #ms

    def __init__(self, title='Simon Memory Game'):
        self.master = tk.Tk()
        self.master.title(title)
        self.master.resizable(False, False)
        self.title = title
        self.buttons = [
            tk.Button(
                self.master,
                height=15,
                width=25,
                background=c,
                activebackground=c,  # remove this line if you want the player to see which button is hovered
                command=partial(self.push, i))
            for i, c in enumerate(self.IDLE)]
        for i, button in enumerate(self.buttons):
            button.grid({'column': i % 2, 'row': i // 2})

    def reset(self):
        self.sequence = []
        self.new_color()

    def push(self, index):
        if index == self.current:
            try:
                self.current = next(self.iterator)
            except StopIteration:
                self.master.title('{} - Score: {}'
                                  .format(self.title, len(self.sequence)))
                self.new_color()
        else:
            self.master.title('{} - Game Over! | Final Score: {}'
                              .format(self.title, len(self.sequence)))
            self.reset()

    def new_color(self):
        for button in self.buttons:
            button.config(state=tk.DISABLED)
        color = random.randrange(0, len(self.buttons))
        self.sequence.append(color)
        self.iterator = iter(self.sequence)
        self.show_tile()

    def show_tile(self):
        try:
            id = next(self.iterator)
        except StopIteration:
            # No more tiles to show, start waiting for user input
            self.iterator = iter(self.sequence)
            self.current = next(self.iterator)
            for button in self.buttons:
                button.config(state=tk.NORMAL)
        else:
            self.buttons[id].config(background=self.TINTED[id])
            self.master.after(self.FLASH_ON, self.hide_tile)

    def hide_tile(self):
        for button, color in zip(self.buttons, self.IDLE):
            button.config(background=color)
        self.master.after(self.FLASH_OFF, self.show_tile)

    def run(self):
        self.reset()
        self.master.mainloop()


if __name__ == '__main__':
    game = Simon()
    game.run()