I will try to answer some of your questions based on my findings for far as I am in the process of modifying 3 webapps to be GDPR compliant and I am also starting a side project.

IANAL and please take this as a starting point. I am not sure that what I understood is correct, but I read the GDPR and this is what I will implement.

> What is personal information

The definition for this is here [0].

What I am doing is I am creating some docs where I write very clearly what information I use and for what.

For existing projects I am looking in schema.db and models and extract from there. For the new one (which will be in Rails) I am thinking to make a gem like annotate or something for this specific purpose.

Also I am documenting the information that is in logs and I will treat most of the information the same way I am treating passwords. So far I am looking for SQL statements, params and custom logging messages.

> Say I have a table with user_id and username, and an order table with user_id, order_id and other other stuff. If the user request a 'forget me', what do I delete

Nothing so far if the user_id and username are not related in any ways to anything that can identify a person.

> To what extent can users be forced to give consent or be denied from a service?

Here is the phrasing from the GDPR [1]:
“the request for consent shall be presented in a manner which is clearly distinguishable from the other matters, in an intelligible and easily accessible form, using clear and plain language.”
So in my opinion this is very different that the Cookie Law as you must make sure the subject understands for what the consent has been given. You should also take a look at Recital 42 and 43 in the beginning of the GDPR where they talk about “consent freely given” and they describe also an imbalance relation between the controller and the user.

> "Export data" / "See all my data" - What is 'all my data'

This is part of Article 15 and I think the situation you are describing is defined by item (3) of that Article. You should correlate it with the definition of personal data.
This means that you should provide data you took from the personal data subject but also the personal data you got from anywhere else that is connected to the data subject - see “personal data are collected from the data subject” and “personal data have not been obtained from the data subject” as it is described in the titles of Article 14 and Article 15.

> “I accept the terms and conditions” would no longer be sufficient to claim that the user has given their consent for processing their data."

Consent cannot be included in the Terms and Conditions. Due to the Recital 42 in the beginning “consent should not be regarded as freely given if the data subject has no genuine or free choice or is unable to refuse or withdraw consent without detriment” and also “safeguards should ensure that the data subject is aware of the fact that and the extent to which consent is given”

> My tax agency requires me to keep records of orders/sales/invoices up to 5 years ago. If a user requests deleting their personal information within that time period, what should I do?

You keep them. Article 17, item (3) states that “shall not apply to the extent that processing is necessary” and you should take a look at letter (b) “for compliance with a legal obligation which requires processing by Union or Member State law to which the controller is subject”

> "Forget me" - Say an employee leaves a company, and they request their personal information to be deleted.

You I think you should delete everything that is not a subject of the law and that it cannot be used “for the establishment, exercise or defence of legal claims”.

Regarding Git or commits for me it is clear that they will not be deleted as there are part of “the purposes for which they were collected or otherwise processed”. If they are part of a project which is part of a legal contract with some users or beneficiary then also it is ok not to delete the GIT commits because you need the info “for the exercise or defence of legal claims” in case anyone will ask in a court who did that feature and when.

To be 100% sure one way will be to anonymise Git user (did not try that so far) by changing the username to something generated like “user0000113” and email associated with that account.

[0] - http://eur-lex.europa.eu/legal-content/EN/TXT/HTML/?uri=CELE... - Article 4, item (1)

[1] - http://eur-lex.europa.eu/legal-content/EN/TXT/HTML/?uri=CELE... - Artile 7, item (2)

edit: formatting